Алгоритмические приложения эллиптических кривых, задаваемых системами уравнений тема автореферата и диссертации по математике, 01.01.06 ВАК РФ



На правах рукописи

Нестеренко Алексей Юрьевич

АЛГОРИТМИЧЕСКИЕ ПРИЛОЖЕНИЯ ЭЛЛИПТИЧЕСКИХ

КРИВЫХ,

ЗАДАВАЕМЫХ СИСТЕМАМИ УРАВНЕНИЙ

01.01.06 - математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

□03489520

Москва 2009

003489520

Работа выполнена на кафедре теории чисел математического факультета Мое ковского педагогического государственного университета

Научный руководитель

доктор физико-математических наук, профессор Чирский Владимир Григорьевич

Официальные оппоненты

доктор физико-математических наук, доцент Алиев Физули Камилович

кандидат физико-математических наук, доцент Макаров Юрий Николаевич

Защита диссертации состоится «18» января 2010 года в 16 часов на засед нии Диссертационного совета Д 212.154.32 при Московском педагогическом гос дарственном университете по адресу: 107140, Москва, ул. Краснопрудная, д. 1 МПГУ, математический факультет, ауд. 301.

С диссертацией можно ознакомиться в библиотеке МПГУ по адресу: 1194 Москва, ул. Малая Пироговская, д. 1.

Автореферат разослан «_»_20 года.

Ученый секретарь

Ведущая организация

Брянский государственный технический университет

диссертационного совета

Муравьева О

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы.

Последние десятилетия научных исследований в области алгоритмической теории чисел показали большую востребованность математического аппарата эллиптических кривых в решении сложных теоретико-числовых задач. Среди таких задач стоит отметить задачу разложения больших целых чисел на множители или задачу доказательства простоты больших натуральных чисел. Эллиптические кривые востребованы в различных прикладных областях математики, к которым можно отнести криптографию и теорию кодирования информации.

Хорошо известно, что эллиптические кривые могут быть заданы при помощи нескольких различных способов, например, в виде плоской кривой в форме Вейерштрасса или пересечения двух поверхностей в трехмерном пространстве. Каждый из способов позволяет исследовать новые свойства, которые могут быть использованы для решения поставленных задач.

В диссертационной работе рассматриваются эллиптические кривые, задаваемые системами уравнений второй степени. Этот способ тесно связан с соотношениями, которым удовлетворяют тэта-функции К-Якоби1 и представляется недостаточно хорошо изученным, с точки зрения его приложений к алгоритмическим вопросам теории чисел.

Основное внимание в диссертационной работе уделено трем вопросам: вычислению целочисленных решений системы связанных уравнений Пелля, задаче определения порядка группы точек эллиптической кривой, заданной системой уравнений уравнений второй степени и разработке метода разложения больших целых чисел на множители с использованием эллиптических кривых, заданных системами уравнений.

Впервые метод решения систем связанных уравнений Пелля был предложен в 1969 году в публикации А.Бейкера и Г. Дэвенпорта2. Далее метод развивался в работах Г. Гринстида3, Р. Пинча4 и В. Англина5.

Нами предложена модификация данного метода, использующая оценку Е.М. Матвеева6 для формы от трех логарифмов алгебраических чисел и позволившая разработать эффективный алгоритм поиска решений. Данный алгоритм был реализован нами на ЭВМ и позволил получить в явном виде решения ряда систем.

Вопрос о вычислении порядка группы точек кривой, заданной в короткой форме Вейерштрасса считается решенным. Алгоритм вычисления порядка группы

1Мамфорд Д. Лекции о тэта-функциях. — Н.:НФМИ, 1998. — 440 с.

1 Baker A., Davenport Я. The Equations Зх3 -2 = у3 and &I3 - 7 = г5 // The Quaterly Journal of Mathematics, Oxford. - 1969. - V.20, №78.

3 Grinstead C.M. On a Method of Solving a Class of Diophantine Equations // Math. Comp. - 1978. — V.32. -p. 936-940.

4Pinch R.G.E. Simultaneous Pell Equations// Math.Proc. Cambridge Philos. Soc. — V.103. — 1988. — p.35-46.

üAnglm W.S. Simultaneous Pell Equations // Math. Comp. - 1996. - V.65, № 213. - p.355-359.

8Матвеев Е.М. Явная важная оценка однородной рациональной линейной формы от логарифмов алгебраиЛ ческих чисел. П // Матем. сб. — 2000. — том.64, №6. — стр.125-180.

L

был предложен в 1985 году Р. Шуфом7 8 и, позднее, модифицирован А. Аткиным и Н. Элкисом9.

Нами приводятся доказательства теорем, из которых следует, что вопрос об определении порядка группы точек эллиптической кривой, заданной системой уравнений второй степени, может быть сведен к определению порядка некоторой кривой, заданной в короткой форме Вейерштрасса.

Мы приводим три различных подхода к доказательству данного результата. Первый подход основан на методе, предложенным Дойрингом для вычисления порядка эллиптической кривой в форме Вейрштрасса. Второй — на представлении порядка эллиптической кривой, заданной системой уравнений, в виде сумм символов Лежандра, взятых отдельно по квадратичным вычетам и квадратичным невычетам по модулю простого числа. Третий подход основан на построении явного отображения точек одной кривой в точки другой.

В третьей главе диссертации мы рассматриваем задачу разложения больших целых чисел на множители. В 1985 году X. Ленстра10 предложил алгоритм факторизации, использующий вычисления с эллиптическими кривыми. Поскольку оценка трудоемкости данного алгоритма зависит от величины наименьшего делителя раскладываемого на множители числа, алгоритм X. Ленстры используется используется в качестве составной части в других алгоритмах, например, в алгоритмах квадратичного решета1112 или решета числового поля1314. Позднее алгоритм Ленстры был модифицирован в статьях П. Монтгомери15, Р. Брента16, а также работе братьев Чудновских17.

Нами описывается оригинальный алгоритм факторизации, использующий вычисления с эллиптическоми кривыми, задаваемыми системами уравнений, развивающий идеи Х.Ленстры и Р.Брента. Получена асимптотическая оценка трудоемкости изложенного алгоритма и приведены точные значения параметров алгоритма, позволяющие снизить оценку трудоемкости при некоторых ограничениях на размер факторизуемого числа.

7 Schoof R. Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p // Math. Сотр. — V.44. - 1985. - p.483-494.

8Schoof R. Counting Points On Elliptic Curves Over Finite Fields // J. Theorie des Nombres de Bordeaux. — Vol. 7. - 1995. - p.219-254.

9 Dewaghe L. Remarks on the Schoof-Elkies-Atkm algorithm. - Math. Сотр. — V.67. -1998. - p.1247-1252.

1Qienstra B. W. Factoring Integers with Elliptic Curves // Ann. Math. - 1987. — № 126. — p.649-673.

nPomerance C. The Quadratic Sieve Factoring Algorithm // EUROCRYPT-84. - Lecture Notes in Computer Science, 209. - Springer-Veriag. — 1985. - pp.169-182.

"Silverman R. The Multiple Polynomial Quadratic Sieve // Math. Of Сотр. — V.48. — 1987. - p.329-339.

13Lemtra A.K. and Lenstra ff. W., Jr.. The Development of The Number Field Sieve. — Lecture Notes in Math, 1554. - Springer -1993.

"Pomerance C. A Tale of Two Sieves// Notices of the AMS. - V.43. - 1996. p.1473-1485.

K Montgomery P.L. Speeding The Pollard and Elliptic Curve Methods of Factorization // Math, of Сотр. — 1987. - Vol. 48. - № 177. - P. 243-267.

16Brent R.P. Some Integer Factorization Algorithms Using Elliptic Curves // Australian Computer Science Communacations. — 1986. — № 8. — p. 149-163.

17 Chudnovsky D., Chudnovsky G. Sequences of Numbers Generated by Addition in Formal Groups and New Primality and Factorization tests // Advances in Applied Mathematics. — 1987. — № 7. — p. 385-434.

SL

Научная новизна работы.

Основные результаты, полученные в диссертации, являются новыми и состоят в следующем.

• Разработан оригинальный алгоритм нахождения целочисленных решений систем связанных уравнений Пелля.

• Доказано равенство порядков групп точек эллиптической кривой, заданной системой уравнений, и эллиптических кривых, заданных в форме Якоби и Вейерштрасса.

• Разработан новый вариант алгоритма Ленстры разложения больших целых чисел на множители, использующий вычисления с эллиптическими кривыми, задаваемыми системами уравнений.

Все разработанные автором диссертации алгоритмы реализованы им лично на ЭВМ, что позволило в явном виде получить решения поставленных задач.

Методы исследования.

В диссертации используются методы теории оценок линейных форм от логарифмов алгебраических чисел, теория непрерывных дробей, методы оценок сумм квадратиченых вычетов, методы теории сложности, а также результаты о числе гладких чисел в заданном интервале.

Теоретическая и практическая ценность.

Диссертация носит теоретический и прикладной характер. Ее результаты могут имеют приложения в дифференциальной геометрии, а также в некоторых областях теории кодирования и криптографии.

Алпробация работы.

Результаты диссертации докладывались автором на научном семинаре механико-математического факультета МГУ им.М.В. Ломоносова, а также на следующих научных конференциях конференциях:

• IV Международной конференции «Современные проблемы теории чисел и ее приложения» (Тула, 2001 г.)

• Конференции «Математика и безопасность информационных технологий» в МГУ им. М.В. Ломоносова (Москва, 2003 г. и 2004 г.)

• VII международной научно-технической конференции «Новые информационные технологии и системы» (Пенза, 2006 г.)

• III международной конференции по проблемам безопасности и противодействия терроризму в МГУ им. М.В. Ломоносова (Москва, 2007 г)

Публикации.

Результаты диссертации опубликованы в 8 работах, список которых приводится в конце автореферата.

Структура диссертации.

Диссертация состоит из введения, трех глав, заключения, библиографического списка, включающеего 44 наименования, и приложения, в котором приведены точные решения ряда систем связанных уравнений Пелля. Общий объем диссертации 65 страниц.

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

В первой главе описывается алгоритм, позволяющий находить целочисленные решения системы связанных уравнений Пелля или, по-другому, тройки целых чисел (х,у,г) удовлетворяющих системе

х2 — (2к + \)г2 — к2 у2 - (21 + 1)г2 = Р

(1)

где параметры I, к- различные натуральные числа. Отметим, что мы ищем только положительные решения системы (1).

Легко видеть, что система (1) имеет две тривиальные тройки решений - (к, 1,0) и (к + 1,1 + 1,1). Поиску всех остальных решений посвящена первая глава диссертации.

Решения первого уравнения системы представляются в виде

х + гу/2 к + 1 =

где £и а 6 (2(\/2А; + 1), |^(а)| = к"2, а б! единица модуля {1, у/2 к +1}. Из этого равенства можно получить выражение для переменной г

г = \ \ п€Ъ, (2)

где а — число сопряженное к а € Щл/2к + 1). Аналогично, из второго уравнения системы (1), можно получить равенство

да-ж

2 = Г.2 Г 2 6 2 /3)

2^/21 + 1 К

где £2,(3 € <0!(\/2£ + 1), = I2, Р число, сопряженное к /3, а £2 единица модуля

{1,^21+1}.

Будем считать, без ограничения общности, что выполнено неравенство £1 < е^. Кроме того, выполнены следующие свойства

£{ >1, ё< = е,-1, г = 1,2,

а также

V7C — I-2 л лчП I4R — /2

= а,а > О, ßß = ß,ß>0. Приравнивая правые части в равенствах (2) и (3) ми получаем соотношение,

связывающее введенные нами параметры

ае in /fe2m 5ёГ /fea"

V2ÄT+T v/2lTi V^F+T V^T+T

(4)

Если найдутся целые индексы пат, удовлетворяющие этому соотношению, то мы сможем вычислить значение z, и далее х, у. В диссертации показано, что в случае выполнения равенства (4) индексы тг и т ограничены, а оценка может быть эффективно определена.

Поскольку z > 0, то из (2) и (3) вытекают нижние оценки для индексов пит

п^Ни т > Яг,

где Hi, #2 наименьшие целые числа, удовлетворяющие неравенствам

log5-logg log?-log/? . .

-Hl ^ ——-, и Ü2 & —7Ti-• W

21og£! 2 log Gl

Для вывода верхней оценки мы воспользовались теорией линейных форм от логарифмов алгебраических чисел.

Определим R, как наименьшее целое число, удовлетворяющее неравенству

Я>тах{0,2Яь2Я2}, (6)

тогда верна следующая

Лемма 1. Пусть выполнено неравенство £j < е2 и п > R, т^ R. Тогда существует константа D, зависящая от к и I, такая что либо D > т ^ п, либо п > т. Можно выбрать D как наименьшее целое, удовлетворяющее неравен•

ству _

|log7i+log(2(*+ /) + !) _ ау/Й+Т log£2 - log£i ' ßV2k+T'

Рассмотрим линейную форму от трех логарифмов

Л = пlog£у -тlog£2 + log7, (8)

где 7 определяется утверждением леммы (1), и определим С следующим образом

С-ш^АД+Ь^Ш), (9)

где величина R определяется из неравенства (6), а величина D - из неравенства (7). Далее, мы будем рассматривать случай, когда п> С. Если это неверно, то мы автоматически получаем оценку сверху для индекса п. При п > С мы получаем верхнюю оценку линейной формы

|Л|<еГ- (Ю)

Для получения нижней оценки модуля линейной формы (8) в диссертации автором используется оценка Е.Матвеева, примененная к линейной форме от трех логарифмов. Введем обозначения

Mi = max (ay/21 + 1, /?\/2к + l) , М2 = max (a\/2l + 1, ¡3^2к + l) ,

Мз — max (aV2l + 1, pVW+l) , ЛЬ- max (ay/21 + 1, 0y/2 к +1) .

и определим параметр A^ как наименьшее действительное число, удовлетворяющее неравенству

A3 > max

Обозначим

А* \

3 = таХ{С'21^|' М

где С определено равенством (9). Далее мы будем считать, что п > Я. В противном случае, мы получаем оценку сверху для п.

Воспользовавшись теоремой Матвеева, мы получаем нижнюю оценку модуля линейной формы (8)

1о8|Л| > -3.1 * 10й (21оё£1) (21ое£2) АзН (78П^£2)'

Учитывая для Л верхнюю оценку (10), получаем неравенство

С^С^п) > п, где С1 = 1.24*10121о8£2Л3, С2 =

Аз

Обозначим через N максимальное из целых чисел, удовлетворяющих приведенному неравенству, а именно,

N - тах {п€2: С^одСгп) > п}. (12)

Таким образом доказана следующая

б

Теорема 1. Пусть z 6 Z неотрицательное решение системы уравнений (1), удовлетворяющее равенству (4). Кроме того, известно, что ei < £2, тогда для индексов п,т. б Z выполнены неравенства

Hi^n^ таx(S, N), #2 ^ тп < max(S, N),

где Hi,H2 определены согласно (5), S - согласно (11), а N - согласно (12).

В диссертации приводится итерационный алгоритм, позволяющий значительно уменьшить верхнюю оценку, в случае, если она совпадает со значением N.

Определим функцию || • || - как расстояние до ближайшего целого числа, то есть, ||£|| = min (\п - где п € Z,£ € К). Нами доказана следующая

Лемма 2. Пусть положительные числа, удовлетворяющие условию \+(м < 1, Далее, пусть д - действительные числа, aq - натуральное. Тогда для любого

п € Z такого, что 1 < п < А

м

ihi

выполнено неравенство

IM

Рассмотрим линейную форму от трех логарифмов (8), по прежнему предполо-гая, что £1 < е2. Выделяя в линейной форме отдельно индекс т, получим модуль

П-,--т +

Л

log £2

log £2 log £2 Таким образом, т является ближайшим целым к величине

пд + где $ =

logei

и i =

log 7

1оБ£2

Поскольку ■д иррационально, мы вычисляем бесконечную непрерывную дробь и, соответственно, подходящую дробь с заранее заданной точностью, а именно, для любого натурального в > 1 выполнено неравенство

1

Ь.

Яа

Я$Яв+1

где & (3-я подходящая дробь. При этом, величина ограничена сверху дробью

и может принимать сколь угодно малые значения.

Опишем итерационный алгоритм позволяющий понизить оценку сверху для индекса п, полученную в утверждении теоремы 1. Пусть п < Л',-, г = 0,1,..., тогда вычисляя подходящую дробь для 1? находим такое значение з, для которого выполнено неравенство

N. < 1. Ш 2

Выберем параметры Аид равными -. Поскольку 1 < п < JVj, то, согласно лемме 2, для найденного индекса а выполнено неравенство

и+ill МП.

С другой стороны, учитывая полученную ранее вехнюю оценку модуля линейной формы (10) и то, что + \/2( + 1 > е, получим неравенство

Н + СИ = И ~ m + £1 < < ¿Г"-

log £2

Объединяя приведенные выше оценки, получим неравенство, относительно п, позволяющее определить новую оценку JVi+j

n < (log£i)_1 log (J^) =: iVi+1. (13)

Пусть константы TV, 5 удовлетворяют утверждению теоремы 1. Тогда, определив в качестве начального значения No := N, получим последовательность оценок Ni, N2,... Вычисления будем производить до тех пор, пока для некоторого номера i не выполнено либо Ni+\ > Ni, либо N¡+1 < S. Тогда искомой оценкой будет

max(n, т) < max(S, Ni), при некотором целом значении индекса i ^ 0. Перебирая все значения п,т в указанном интервале, в случае выполнения равенства (4), мы получаем решения исходной системы уравнений (1).

Алгоритм, изложенный выше, реализован автором на ЭВМ. Были решены все системы вида (1), где к и I удовлетворяют неравенствам 1 < к < I < 100. Полученные решения приведены в приложении к диссертационной работе.

Содержание второй главы.

Во второй главе диссертационной работы рассматривается система сравнений

f u? + «3sl (mod р), , .

Ла'~ \Au? + u|=1 (mod р),

где р > 3 простое число, и А =Ё 0,1 (mod р).

Мы показываем, что найдется несколько различных эллиптических кривых, заданных в форме Вейерштрасса, порядок группы точек которых совпадает с порядком кривой S\.

Рассмотрим эллиптическую кривую, заданную в форме К. Якоби сравнением

Ех-. у2==ф- 1)(*-А) (mod р), - (15)

где А удовлетворяет тем же ограничениям: А ф 0,1 (mod р).

Мы будем обозначать символом порядок произвольной группы Е. Тогда верна следующая

Теорема 2. Для порядков рассматриваемых нами абелевых групп S\ и Е\ выполнено равенство |5д| = \Е\\.

Рассмотрим эллиптическую кривую F\, заданную сравнением

Fx-. у2 = я3 — ^(1 + 14Л + Х2)х — — ЗЗА — ЗЗА2 + Л3) (mod р), (16)

о Л{

где А удовлетворяет все тем же ограничениям: А 0,1 (mod р).

Мы строим отображение элементов группы <5д на множество точек эллиптической кривой Fx и доказываем результат, аналогичный теореме 2.

Теорема 3. Выполнено равенство |5д| = |JF\|-

Приведем наброски доказательств сформулированных теорем: два для доказательства теоремы 2 и один для теоремы 3.

При доказательстве теоремы 2 мы провели следующие рассуждения. Для значения |.Ед| верно сравнение

т

\Ex\ = l~D^(X) (mod р), где Dm(X) = (~1)т £ (С?)2 \\ (17)

fc=0

и С™ — н(т-ку ~~ биномиальный коэффициент. Для значения [£>д| верно равенство

\Sx\=P+l+(jj+Si, (18)

где значение $з определяется равенством S3 = J^ljj ^ " ^ А" ^ и удовлетворяет сравнению S3 = -De^i(A) - ^^ (mod р). Следовательно |5а| = 1-1)¥(А) = |£д| (mod р).

^ 4^/р из которой

Далее, мы получем оценку ||5д) — |-Ех|| =

следует, что значения |£д| и |5д| совпадают,

В диссертации мы приводим второе доказательство теоремы 2. Определим символом N0 число решения системы

u2 + tí2 = Q: (mod р), Хи\ + ul = a (mod р).

(19)

Лемма 3. Пусть а произвольный квадратичный невычет по модулю р. Тогда выполнено равенство Af\+Na — 2(р+1—.Afc), где Л/"оо число бесконечно удаленных точек кривой 5д.

Для значения |£д| выполнено равенство

|£x| = P + l + Ei + Ej, где

Sl== £ M*-*)(*•-J2 М*-1^-^4),

х - кв. вычет ^ Р ' х - кв. невычет \ Р s

(суммирование ведется отдельно по квадратичным вычетам и квадратичным невычетам). Мы показали, что для произвольного квадратичного невычета а выполнены равенства

Подставляя значение Ма из утверждения леммы 3, получим равенство

|Яа1 = Р +1 + 5 (М - [2(р +1 - AU - M]) = M + M* = |5a|,

которое завершает доказательство теоремы.

При доказательстве теоремы 3 следующие рассуждения. Определим отображение точек кривой «Sa на эллиптическую кривую F\ равенствами

X ^ + (modp)) (20)

о U\ +1

2(1 - Л) , , , у - (Ц1 + 1)2ц2"з (mod р).

и введем обозначение f(x) = х3 - ¿(1 + 14Л+Л2)х - - ЗЗА - ЗЗЛ2 + А3). Тогда для порядка |Fa| будет выполнено

«-'♦gK?))-'*"!^)-

Замечая, что выполнено равенство / = 4А(А — I)2, а также Р~2 //л ..i\ti \..ч\ Р-1

g /(1 - и2)(1 — Ам2\ = g /(1 — и2)(1 — Ац2\ U=0 \ Р s U=0 ^ Р '

получаем |Fa| = р+1+^^ +5з = |5д|, где сумма <S3 определяется выше. Теорема

3 доказана.

Содержание третьей главы.

В третьей главе диссертации излагается оригинальный алгоритм разложения на множители натурального числа N, оснований на идеях Х.Ленстры и Р.Брента. Алгоритм использует вычисления с эллиптической кривой S\, заданной в проективной форме системой сравнений

*<*•>■■{*К <21)

где А?* 0,1 (mod. N).

Пусть х = (xi : Х2 '■ хз : xt) и у — (уг : У2 : Уз '■ У*) произвольные решения системы (21). Используя формулы для сложения точек на кривой <Sx, определим бинарную операцию © на множестве S\(Z^). Если выполнено равенство

(2/1:2/2 : 2/3: Vi) = (xi : £ix2 : е2х3 : е^г^), где еь е2 = ±1 (mod N), то определим w = (w\: w2: w3 : Wi) = x Ф у соотношениями

Щ = £i£2 • 2xix2^3^4 (mod N), Щ = £2 • (^г1! ~ я^з) (mod JV), W3 ~ ei • (13I4 - Axfif) (mod JV), гУ4 = (x\ - Xxf) (mod N),

(22)

в противном случае определим

' Щ = (хЪз ~ хЫ) (mod N), w2 = (xix2y3y4 - x3x4yiy2) (mod N), w3 = (х1х3у2у4 - x2x4yiy3) (mod N), Wi = (xix4y2y3 - 12X31/12/4) (mod N).

(23)

Определение 1. Пусть m £ N. Мы будем называть бинарную операцию © операцией <гпсевдо» сложения решений системы (21) и использовать обозначение

т-х = (х фх)фх...фх, xeS\(Ztf). (24)

s ■v '

тцлз

Выберем произвольное множество S\(Zu) и некоторое ненулевое решение х € ¿>a(Zлг) системы (21). Тогда выполнено сравнение

NpX s о (mod р), (25)

если p\N и Np порядок эллиптической кривой S\(fp), определенной над конечным полем Fp.

Обозначим AfpX — {w\ : w2 : : W4). Поскольку нулевой элемент группы <Sa(Fp) — точка о € Sa(Fp) определена равенством о = (0 :1:1:1), то выполнено

II

сравнение wi = 0 (mod р). В этом случае, если Wi ф О (mod N), мы можем найти делитель числа N вычислив

НОД (wi, N) ~р.

Поскольку точное значение Л/J, нам не известно, то мы выберем некоторое достаточно большое целое число тп € N такое, что с большой вероятностью будет выполнено Np\m. Тогда из (25) вытекает

тпх = о (mod р). (26)

При практической реализации алгоритма значение m выбирается в виде произведения

j=i

где pj е N — все маленькие простые числа18 2,3,5, ..., не превосходя-

щие некоторой постоянной границы bi € N, и степени щ € N имеют небольшие значения.

В качестве Ь\ выбирается некоторая постоянная, зависящая от р — простого делителя числа N. В диссертации показано, что в качестве bi можно выбрать величину L^pJ, Для некоторого а € R, а > 1.

Если после вычисления соотношения (26) делитель числа N не найден, то мы выбираем другое множество S\(Zn), с новым значением параметра А.

Вычисление соотношения (26) является первым этапом нашего алгоритма факторизации. Для увеличения вероятности нахождения решения, мы предлагаем использовать второй этап. Предположим, что существует простое число рь такое, что

h<Pk<:b2, PkWp, и | то, (27)

Рк

где Ьч € N некоторая постоянная, ¿>2 > bi, тогда равенство

(рктп) х = о (mod р),

аналогично (26), позволяет найти делитель числа N.

Используемый нами вариант второго этапа алгоритма сводится к случаному выбору простых чисел Рк в заданном интервале. В диссертации, мы получаем оценку на величину данного интервала, минимизирующую трудоемкость алгоритма в целом.

Дополнительно мы вводим еще два параметра алгоритма: параметр Ьз определяет количество систем ¿>а(2дг), используемых в алгоритме, параметр Ьд определяет количество простых чисел рк, перебираемых на втором этапе алгоритма.

"Напомним, что функция ж(х), х е N, определяет число простых чисел, не превосходящих т.

12.

Алгоритм 1. (Алгоритм разложения на множители)

Вход: Составное число N, НОД (6, N) = 1.

Выход: Целое число р такое, что р ¡N, либо заключение о неудаче.

1. Выбрать параметры алгоритма 61,63,63,64 6 N, а также целое число т € N.

2. Выбрать произвольное A G Zjv, А ^ 0,1 (mod N), и ненулевое решение системы (21)

х е sx(xN).

3. С использованием (24) вычислить точку w = (v)\ : w2: w3 : ш4), где w = mx.

4. Вычислить d = НОД (tiij, ЛГ). Если 1 < d < N, то завершить работу алгоритма.

5. Определить к = 1.

6. пока А: ^ 64 выполнять

6.1. Случайным образом выбрать простое число р*, bi < рь 4. k, и вычислить точку

z = P),w, z = (г!: Ъ : г3 : г4).

6.2. Вычислить d — НОД (zi, N). Если 1 < d < N, то завершить работу алгоритма.

6.3. Вычислить к = к + 1.

7. Вычислить j = j + l. Если j ^ Ьз, то вернуться на шаг 2). В противном случае, завершить

работу с уведомлением о неудаче. ►

Предложенный алгоритм является параметрическим и носит вероятностный характер - существует вероятность того, что решение не будет найдено после выполнения всех шагов алгоритма.

В диссертации получена верхняя оценка трудоемкости данного алгоритма Т, оценивающая количество элементарных операций с целыми числами, не превосходящими величины факторизуемого числа N

(

Т<Ь3

7+(с2 + с1)ЫМ+с31пС\\СбЬ1+с,+

4-■—v—--' . 1п2

\

2-Й шаг

\

+ С11пЛг + 64 In b2 + C4 + Ciln-W) , \1п2 Л

(28)

/

Полученная оценка зависит от значения числа N и параметров алгоритма 61, 62, 63,64. Значения используемых констант сх,..., се приведены в тексте диссертации и зависят от трудоемкости алгоритмов, реализующих элементарные операции с большими целыми числами.

Для оценки асимптотической оценки приведенного алгоритма в диссертации доказана следующая

Теорема 4. Пусть параметры 61,62,63,64 алгоритма 1 таковы, что

I О 1п п

1. выполнено 61 = ?Гр и Ьз = еа1аа, где а = ч/——,

V шшр

выполнено Ь,<Ь,ик< Д^Й)-

Пусть найдется такая действительная константа сщ > 1, что Сю1пр < 1пЛГ при N —юо, р -+ оо. Тогда трудоемкость алгоритма 1 не превосходит

операций в кольце Ък, где с? —

Для определения точных значений параметров алгоритма 1 рассмотрим действительное число /3, а > /3 > 1, и определим параметр 62 равенством

Ь = (29)

Тогда выполнено неравенство < ., которое позволяет получить

-«у^+Ш 2(С4+С1Сю Шр)

верхнюю оценку д ля Ьц в зависимости от параметра /3.

Легко видеть, что максимальное значение ¿>4 достигается при (3 — а. Однако, при таком выборе ¡3 интервал (%/р, ^¡/р) не содержит простых чисел. Поэтому мы наложим еще одно ограничение на парамер 64, а именно

врШ _ а«1/«

Ьа < 7г(6г) - »(Ьх) ~ 0 - = И ■ (30)

Из (30) следует, что при /3 = 1 параметр 64 принимает максимальное значение.

Таким образом, для определения значения /3, при котором 64 принимает максимальное значение, необходимо решить уравнение

Рр1/0 - ар1/а _ с41п2 + с3Ьс5 + С3С6Ь1

ЬР ~^Р + 1П2(С4 + С1С10111Р)"

С использованием ЭВМ мы нашли значения /3 и, соответствующие им значения 62, удовлетворяющие данному уравнению при заданных ограничениях на величину делителя р и некоторых значениях константы сю- Результаты вычислений, содержатся в тексте диссертации.

Алгоритм 1 был реализован автором диссертации на ЭВМ. Был проведен ряд экспериментов, целью которых являлась оценка вероятности успешного завершения алгоритма при рассчитанных значениях параметров. Одно и тоже число подвергалось многократному разложению и проводился сравнительный анализ полученных значений с рассчитанными заранее значениями.

Приведем один из нескольких результатов, полученных в ходе практических экспериментов. Мы факторизовали число

N = 142657541002063195275367942016858713253, = 128.

Символом р мы обозначаем наименьший делитель числа символом 5 количество попыток факторизации. Столбцы «Шаг 4» и «Шаг 6» показывают процент

14

успешного разложения на четвертом и, соответственно, шестом шагах алгоритма. Параметр min определяет минимальное число попыток выбора случайного решения на втором шаге алгоритма, потребовавшихся для успешной факторизации, cnt — количество успешных разложений с минимальным числом попыток, тех — максимальное число попыток, в случае успешного разложения. Параметр avg определяет среднее число попыток, необходимых для успешного разложения на множители (в процентах от значения 63).

bg2(p) S Шаг 4 Шаг 6 h min 1 cnt max avg

64 100 67(67%) 33 (33%) 476 1 2(2%) 429 82.24 (18%)

Как следует из приведенных значений, среднее число успешных попыток существенно меньше, чем значение параметра 1>з, определяющего максимальное число попыток. С увеличением размерности раскладываемых чисел это значение растет, но не слишком сильно: отношение числа успешных попыток к теоретически рассчитанному не превышает 25%. После проведения большого числа экспериментов, необходимость второго этапа алгоритма (шаг 6) является обоснованной.

Работы по теме диссертации

[1] Нестеренко А.Ю., Нахождение целочисленных решений системы связанных уравнений Пелля // Математические заметки — Том 86 — Вып. 4 — 2009 — стр. 588-600. — 0.8 п.л.

[2] Нестеренко А.Ю. О числе решений одной системы сравнений // Депонировано во ВИНИТИ. - № 4б4-в2009. - 2009. - 17 стр. - 1.02 п.л.

[3] Нестеренко А.Ю. О нахождении целочисленных решений системы связанных уравнений Пелля //IV Международная конференция «Современные проблемы теории чисел и ее приложения» — Тула — 2001 — стр.88. — 0.06 п.л.

[4| Нестеренко А.Ю. О групповых свойствах одной системы уравнений // Материалы конференции «Математика и безопасность информационных технологий» в МГУ 23-24 октября 2003 г. - Издательство «МЦНМО» - Москва - 2004 - стр. 221-222. - 0.12 п.л.

[5] Нестеренко А.Ю. YAQS — еще один алгоритм квадратичного решета // Материалы конференции «Математика и безопасность информационных технологий» в МГУ 2004 г. — Издательство «МЦНМО» — Москва — 2005. — 0.12 п.л.

[6] Нестеренко А.Ю. Схема асимметричного шифрования с возможностью аутентификации // Труды VII Международной научно-технической конференции «Новые информационные технологии и системы» — Пенза — 2006 — стр. 104-107. — 0.42 п.л.

[7] Вельский B.C., Нестеренко А.Ю. Проблемы технологии открытых ключей // Information Security, 2007. - стр. 42. - 0.18 п.л.

[8] Нестеренко А.Ю., Об одном варианте метода Ленсгры факторизации целых чисел // Материалы третьей международной конференции по проблемам безопасности и противодействия терроризму в МГУ 25-27 октября 2007 г. - М,:МЦМНО, 2008. ~ стр. 234-240. - 0.1 п.л.

Подп. к печ. 09.12.2009 Объем 1 п.л. Заказ №. 177 Тир 100 экз. Типография МПГУ

Введение

1 Нахождение целочисленных решений системы связанных уравнений Пелля

1.1 Представление квадратичными формами.

1.2 Оценки числа решений.

1.2.1 Определение максимального индекса.

1.2.2 Верхняя оценка линейной формы.

1.2.3 Нижняя оценка линейной формы.

1.3 Уменьшение верхней оценки

2 О числе решений одной системы сравнений

2.1 Первое доказательство теоремы 2.

2.2 Второе доказательство теоремы 2.

2.3 Доказательство второй теоремы.

2.4 Примеры вычислений.

2.5 Дополнение: построение изогений

3 Об одном варианте метода Ленстры факторизации целых чисел

3.1 Определение кривой над кольцом вычетов

3.2 Алгоритм факторизации.

3.3 Алгоритм построения кривой.

3.4 Об оценке трудоемкости алгоритма

3.4.1 Верхняя оценка трудоемкости алгоритма.

3.4.2 Асимптотическая оценка трудоемкости.

3.5 Результаты вычислений.

Во многих областях математики возникают задачи связанные с поиском решений и исследованием свойств нелинейных систем уравнений. В настоящей диссертационной работе изучаются системы уравнений второй степени от трех неизвестных, коэффициенты которых удовлетворяют некоторым ограничениям и могут принадлежать либо кольцу целых чисел, кольцу вычетов по модулю некоторого целого числа, либо конечному полю, характеристики отличной от двух.

В диссертационной работе мы рассматриваем несколько независимых математических задач, которые возникают в связи с изучением подобных систем уравнений.

В первой главе мы описываем алгоритм поиска всех целочисленных решений систем связанных уравнений Пелля ж2 - (2к + 1)г2 = к2 у2 - (21 + 1)г2 = I2 (1) где параметры к - различные натуральные числа. Поиск решений систем диофантовых уравнений вида (1) интересен не только сам по себе, но и востребован в некоторых задачах дифференциальной геометрии [16].

Впервые метод решения систем диофантовых уравнений подобного вида был предложен в 1969 году в публикации А.Бейкера и Г. Дэвенпор-та [21]. Далее метод развивался в работах Г. Гринстида [27], Р. Пинча [36] и В. Англина [19]. Указанными авторами предлагалось вычислять несколько независимых бесконечных серий решений для каждого из уравнений системы (1) и, рассматривая пересечения, получать оценку сверху для числа возможных решений. Для вывода оценки используется теория линейных форм от логарифмов алгебраических чисел.

Автором предложена модификация данного метода. Используя оценку Е.М.Матвеева [9] для формы от трех логарифмов алгебраических чисел, мы получаем более точные оценки сверху для числа решений системы (1). Более того, предложена итерационная процедура, использующая вычисления с подходящими дробями иррациональных чисел и позволяющая уменьшить полученную ранее оценку.

Предложенный метод был реализован автором на ЭВМ и решены системы вида (1) для всех значений параметров, удовлетворяющих неравенству 1 ^ А: < / ^ 100. Результаты первой главы докладывались автором в 2001 году на IV международной конференции «Современные проблемы теории чисел и ее приложения» [10], научном семинаре кафедры теории чисел механико-математического факультета МГУ. им. М.В.Лоносова в 2002 году и были полностью опубликованы в 2009 году в статье [13].

Вторая глава диссертационной работы посвящена исследованию систем сравнений вида и\ + и\ = 1 (mod р), Хи\ + и\ = 1 (mod р), где параметр Л удовлетворяет условию Л ф 0,1 (mod р) и р > 2 — простое число.

Хорошо известно, см., например, [8, гл. I] или исторический обзор в книге [18], что множество решений данной системы сравнений является эллиптической кривой, то есть абелевой группой. Используя терминологию, принятую в алгебраичекой геометрии, мы будем называть решения системы (2) точками кривой.

В случае, если система (2) рассматривается над полем комплексных чисел, то ее решения могут быть параметризованы эллиптическими функциями К. Якоби [4]. Соотношения, которым удовлетворяют эллиптические функции К. Якоби, позволяют определить на множестве решений системы (2) операцию сложения. Данные соотношения могут быть эффективно реализованы на ЭВМ, что было показано в работах [23, 33]. В 2004 году автором были предложены, см. [II], более эффективные соотношения для определения операции сложения решений рассматриваемых систем сравнений, основанные на свойствах тета-функций К. Якоби.

Основным предметом исследований, отраженных во второй главе диссертационной работы, является вопрос о вычислении порядка группы точек кривой, заданной системой сравнений (2), для заданного значения параметра Л. Для эллиптических кривых, заданных в короткой форме Вейерштрас-са, этот вопрос является решенным. Алгоритм вычисления порядка группы был предложен в 1985 году Р. Шуфом [И, 12] и, позднее, модифицирован А. Аткиным и Н. Элкисом [29].

Во второй главе диссертационной работы автором доказываются теоремы 2.1 и 2.2, из которых следует, что для любой системы сравнений (2) найдутся эллиптические кривые

Е\ \ у2 = х(х - 1)(х - X) (то¿р), (3) у~ =ж3-^(1 + 14Л + А2)я-|-(1-ЗЗА-ЗЗА2 + А-!) (тех! р), (4) о с таким же порядком группы точек. Этот результат позволяет сводить задачу вычисления порядка группы точек кривой (2) к определению порядка одной из перечисленных кривых.

Мы приводим три различных подхода к доказательству существования эллиптической кривой с таким же порядком группы точек. Первый подход основан на методе, предложенным Дойрингом для вычисления порядка эллиптической кривой Е\. Второй — на представлении порядка эллиптической кривой Е\ в виде сумм символов Лежандра, взятых отдельно по квадратичным вычетам и квадратичным невычетам по модулю простого числа р. Оба подхода используются для доказательства теоремы 2.1.

Для доказательства теоремы 2.2 мы используем третий подход — в явном виде строим отображение множества решений системы (2) на множество точек эллиптической кривой Результаты второй главы полностью опубликованы в 2009 году работе [14].

В третьей главе диссертации мы рассматриваем задачу разложения больших целых чисел на множители. В 1985 году [31] X. Ленстра предложил алгоритм поиска делителей целого числа, использующий вычисления с эллиптическими кривыми. Поскольку оценка трудоемкости данного алгоритма зависит от величины наименьшего делителя раскладываемого на множители числа, алгоритм X. Ленстры, обычно, используется используется в качестве составной части в других алгоритмах, например, в алгоритмах квадратичного решета [38, 43] или решета числового поля [32, 39].

В первоначальном варианте алгоритма X. Ленстры предлагалось использовать для факторизации эллиптические кривые, заданные в аффинной форме записи. Позднее, П. Монтгомери [31] предложил использовать проективные координаты эллиптической кривой, а Р. Брент [21] — дополнить алгоритм вторым этапом, увеличивающем вероятность успешного завершения алгоритма. В работе братьев Чудновских [20] было замечено, что для реализации алгоритма можно использовать проективные абелевы многообразия, однако до последнего времени не было известно многообразий, допускающих эффективную реализацию группового закона.

В работе [11] автором была рассмотрена система уравнений, множество решений которой образует абелеву группу. Позднее автор показал, что множество решений рассмотренной системы уравнений может быть сведено к множеству решений хорошо известной системы уравнений аффинная форма которой рассматривалась нами во второй главе настоящей работы. Если решения системы (5) принадлежат некоторому полю, характеристики отличной от двух, то множество решений является эллиптической кривой и образует абелеву группу относительно операции сложения [4, 23, 33].

В третьей главе автором описывается разработанный им алгоритм разложения на множители нечетного, натурального числа N, основаный на идеях Х.Ленстры и Р.Брента и использующий вычисления со множеством решений системы (5) в кольце вычетов Ъм

Автором получена асимптотическая оценка трудоемкости изложенного алгоритма и приведены результаты реализации данного алгоритма на ЭВМ. Приведены точные значения параметров алгоритма, позволяющие снизить оценку трудоемкости при некоторых ограничениях на размер фак-торизуемого числа N.

5)

Результаты третьей главы докладывались на конференции «Математика и безопасность информационных технологий» в 2003 и 2007 годах и опубликованы в работах [11, 12].

Основные результаты, выносимые на защиту. Автором выносятся на защиту следующие основные результаты:

• Алгоритм нахождения целочисленных решений системы (1) связанных уравнений Пел ля.

• Доказательство равенства порядка групп точек эллиптической кривой, заданной системой сравнений (2) и эллиптических кривых, заданных в форме Вейерштрасса соотношениями (3) и (4).

• Новый вариант алгоритма Ленстры разложения больших целых чисел на множители, использующий вычисления с решениями системы уравнений (5) в кольце вычетов Ъ^.

Все выносимые на защиту результаты являются новыми и получены автором самостоятельно. По теме диссертации автором опубликовано 5 научных работ [10, 11, 12, 13, 14].

Диссертация состоит из введения, трех глав, списка литературы и приложения, в котором приведены решения систем связанных уравнений Пел-ля для некоторых значений параметров. Общий объем диссертации составляет 65 страниц.

Заключение

В диссертационной работе рассмотрены задачи, возникающие в связи с исследованием эллиптических кривых, задаваемых системами уравнений второй степени.

В первой главе разработан оригинальный алгоритм нахождения целочисленных решений систем связанных уравнений Пелля. Данный алгоритм математически обоснован и реализован на ЭВМ. Результаты экспериментов приведены в приложении к диссертационной работе.

Во второй главе рассмотрен вопрос о вычислении порядка группы точек эллиптической кривой, задаваемой в форме системы сравнений. Доказан результат о равенстве порядка группы точек рассматриваемой кривой и кривой, заданной в короткой форме Вейерштрасса. При доказательстве использованы два различных подхода, позволяющих в явном виде предъявить отображение множества точек одной кривой во множество точек другой.

В третьей главе предложен новый алгоритм факторизации — разложения больших целых чисел на множители. Алгоритм математически обоснован, получена асимптотическая оценка сложности алгоритма и показано, что она зависит от размера минимального делителя факторизуемого числа. Вычислены точные значения параметров алгоритма, позволяющие минимизировать трудоемкость алгоритма при известных ограничениях на размер мииимального простого делителя раскладываемого на множители числа.

1. Боревич З.И., Шафаревич И.Р. Терпя чисел. — 3-е изд. — М.:Наука, 1985. — 503 с.

2. Венков Б.А. Элементарная теория чисел. Математика в монографиях. Серия обзоров, вып.4. - М.-.ОНТИ НКТП СССР, 1937.

3. Гелъфонд А.О., Линник Ю.В. Элементарные методы в теории чисел.- М.:Физматгиз, 1962. — 272 с.

4. Гурвиц А. Теория аналитических и эллиптических функций. — М.:ГТТИ, 1933. 344 с.

5. Касс&ас Дж. Диофантовы уравнения со специальным рассмотрением эллиптических кривых // Математика, сб. переводов — 1968. — т. 12, вып.2 — стр. 3-48.

6. Кнут Д. Искусство программирования для ЭВМ. Получисленные алгоритмы. — М.:Мир. — 1977.

7. Лет С. Эллиптические функции. — М.:Наука, 1984. — 312 с.

8. Мамфорд Д. Лекции о тэта-функциях. — Н.:НФМИ, 1998. — 440 с.

9. Матвеев Е.М. Явная нижняя оценка однородной рациональной линейной формы от логарифмов алгебраических чисел. II // Матем. сб.2000. — том.64, №6. — стр. 125-180.

10. Нестеренко А.Ю. О нахождении целочисленных решений системы связанных уравнений Пел ля //IV Межд. конф. «Современные проблемы теории чисел и ее приложения», тезисы докладов. — Тула, 2001. 88стр.

11. Нестеренко А.Ю. О групповых свойствах одной системы уравнений // Материалы конференции «Математика и безопасность информационных технологий» в МГУ 23-24 октября 2003 г. — М.:МЦНМО — 2004. стр. 221-222.

12. Нестеренко А.Ю. Об одном варианте метода Ленстры факторизации целых чисел // Материалы третьей международной конференции по проблемам безопасности и противодействия терроризму в МГУ 25-27 октября 2007 г. М.:МЦМНО, 2008. - стр. 234-240.

13. Нестеренко А.Ю. Нахождение целочисленных решений системы связанных уравнений Пелля // Математические заметки. — 2009. — Том 86, вып. 4. — стр.588-600.

14. Нестеренко А.Ю. О числе решений одной системы сравнений // Депонировано во ВИНИТИ. № 454-в2009. - 2009. - 17 стр.

15. Прахар К. Распределение простых чисел. — М.:Мир. — 1967. — 511 с.

16. Сабитов И.Х. Исследование жесткости и неизгибаемости аналитических поверхностей вращения с уплощением в полюсе // Вестник МГУ, 1986. № 5. - стр. 29-36.

17. Хассе Г. Лекции по теории чисел. — М.:ИЛ, 1953. — 527 с.

18. Шафаревич И.Р. Основы алгебраической геометрии. — М.:Наука. — 1972.

19. Anglin W.S. Simultaneous Pell Equations // Math. Comp. — 1996. — V.65, № 213. p.355-359.

20. Baker A. Linear Forms In The Logarithms of Algebraic Numbers // Mathematica. 1968. - V.15. - p.204-216.

21. Baker ADavenport H. The Equations 3x2 2 = y2 and 8x2 - 7 = z2 // The Quaterly Journal of Mathematics, Oxford. — 1969. — V.20, №78.

22. Bennet M.A. On The Number of Solutions of Simultaneous Pell Equations//, Mathematics Subject Classification. — 1991. — preprint.

23. Billet 0., Joye M. The Jacobi Model Of An Elliptic Curve And Side-Channel Analysis. — 2002. — preprint.

24. Brent R.P. Some Integer Factorization Algorithms Using Elliptic Curves // Australian Computer Science Communacations. — 1986. — № 8. — p. 149-163.

25. Brent R.P. Some Integer Factorization Algorithms Using Elliptic Curves. — 1998. — дополненная версия статьи 2 I].

26. Chudnovsky D., Chudnovsky G. Sequences of Numbers Generated by Addition in Formal Groups and New Primality and Factorization tests // Advances in Applied Mathematics. — 1987. — № 7. — p. 385-434.

27. Grinstead C.M. On a Method of Solving a Class of Diophantine Equations // Math. Сотр. 1978. - V.32. - p. 936-940.

28. Davenport H. The Higher Arithmetic. An Introduction to the Theory of Numbers. — NY. — 1952. В русском переводе: Дэвенпорт Г. Высшая арифметика. Введение в теорию чисел. — М.:Наука. — 1965.

29. Dewaghe L. Remarks on the Schoof-Elkies-Atkin algorithm. — Math. Сотр. V.67. - 1998. - p. 1247-1252.

30. Husemoller D. Elliptic Curves. — 2nd Ed. — Springer. — 2004. — 487pp.

31. Lenstra H. W. Factoring Integers with Elliptic Curves // Ann. Math. — 1987. Ш 126. - p.649-673.

32. Lenstra A.K. and Lenstra H. W., Jr. The Development of The Number Field Sieve. — Lecture Notes in Math, 1554. — Springer — 1993.

33. Liardet P., Smart N. Preventing SPA/DMA In ECC Systems Using The Jacobi Form // Cryptographic Hardware and Embedded Systems. — CHES-2001. — Lecture Notes in Computer Science, 2162. — Springer. -2001. -p.391-401.

34. Montgomery P.L. Speeding The Pollard and Elliptic Curve Methods of Factorization // Math, of Comp. — 1987. — Vol. 48. — № 177. — P. 243-267.

35. Montgomery P.L. An FFT Extension of Elliptic Curve Method of Factorization. — University of California. — 1992. — PhD Thesis.

36. Pinch R.G.E. Simultaneous Pell Equations// Math.Proc. Cambridge Philos. Soc. V.103. - 1988. - p.35-46.

37. Pollard J.M. A Monte Carlo Method for Factorisation // BIT. — 1975. № 15. - p.331-334.

38. Pomerance C. The Quadratic Sieve Factoring Algorithm // EUROCRYPT-84. Lecture Notes in Computer Science, 209. -Springer-Verlag. — 1985. - pp. 169-182.

39. Pomerance C. A Tale of Two Sieves// Notices of the AMS. — V.43. — 1996. p.1473-1485.

40. Pomerance C. Two methods in elementary analytic number theory // Number theory and applications / Ed. R.A. Molin. — 1989. — p. 135161.

41. Schoof R. Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p // Math. Comp. — V.44. 1985. - p.483-494.

42. Schoof R. Counting Points On Elliptic Curves Over Finite Fields //J. Theorie des Nombres de Bordeaux. — Vol. 7. — 1995. — p.219-254.

43. Silverman R. The Multiple Polynomial Quadratic Sieve // Math. Of Comp. V.48. - 1987. - p.329-339.

44. Waldschmidt M. A Lower Bound for Linear Forms in Logarithms // Acta Arithmetica. V.37. - 1988. — p.257-283.