Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Прежде чем формулировать аналог предложения VL 3. 1 для Е, заметим, что даже не зная, что п — простое число, можно для сложения элементов из E применять формулы из § 1. При сложении двух точек (или удвоении точки) возможны три случая: 1) мы получаем корректно определенную точку; 2) если точки имеют вид (х,у) и (х,-у) по модулю п, то мы получаем точку в бесконечности; 3) формулы оказываются неопределенными, поскольку встретился знаменатель, не обратимый по модулю п. Однако случай 3) означает, что п — составное число, и мы можем найти его нетривиальный делитель, взяв НОД от п и этого знаменателя. Таким образом, без ущерба для общности мы можем в дальнейшем предполагать, что случай 3) исключен.
Можно показать, что если P — элемент E по модулю п, то даже при составном п ответ, который наш алгоритм дает для тР, не зависит от последовательности сложений или удвоений точек (a priori это не очевидно). Однако этот факт ниже не используется. Достаточно условиться обозначать тР любую точку, полученную из P путем вычислений по модулю п по формулам из § 1.
Вполне аналогично тому, как сложение точек по модулю п можно проводить без предположения о простоте п, можно применить к нашему множеству E по модулю п алгоритм нахождения числа точек на эллиптической кривой (например, метод Шуфа). Мы либо получим некоторое целое т, которое при простом п равно числу точек эллиптической кривой Е, либо столкнемся с неопределенным выражением, знаменатель которого имеет с п нетривиальный общий делитель. Как и в случае сложения точек, без ущерба для общности можно предположить, что последний случай никогда не встречается.
Такое т будет играть роль п — 1 в предложении VI. 3. 1; отметим, что п - 1 — это порядок группы (Z/nZ)*, если п — простое число.
Теперь сформулируем аналог критерия Поклингтона для эллиптических кривых.
Предложение VI. 3.2. Пусть п — натуральное число. Пусть E — множество, определяемое уравнением у2 = х3 + ах + b по моду-
214
ГЛ. VI. ЭЛЛИПТИЧЕСКИЕ КРИВЫЕ
3 2
лю п, как описано выше (и НОД (4а + 27b , n) = 1 — прим. перев.). Пусть т — целое число. Предположим, что у т есть простой делитель q, больший (n1/'4 + I)2. Если существует такая точка P на E, что 1) тР = О и 2) уP определена и не равна О, то п — простое число.
Доказательство (ср. с доказательством предложения VI. 3. 1). Если п — не простое, то у него есть простой делитель р ^ у/п. Пусть Б' — эллиптическая кривая, заданная тем же уравнением, что и Е, но рассматриваемая по модулю р, и пусть т — порядок группы Б'. По теореме Хассе т ^ р + 1 + 2^/р = (^/p + I)2 ^ (п1^4 + I)2 < q и поэтому НОД (q, т ) = 1. Следовательно, существует такое целое и, что uq=l (mod т). Пусть P Є Б' — это точка Р, рассматриваемая по модулю р. Тогда в E' имеем ^P' = uq^P = итР' = О ввиду 1),
так как тР' получается в точности тем же путем, что и тР, только все действия производятся не по модулю п, а по модулю его делителя р. Но это противоречит 2), так как если у P определена и не равна
О по модулю п, то, производя при вычислении уР' те же действия,
только по модулю р, мы должны получить уР' ф О. Предложение доказано.
Это предложение приводит к алгоритму для доказательства простоты данного натурального числа п (о котором уже известно, что оно «вероятно простое»). Действуем следующим образом. Выбираем случайно три целых числа а,х,у по модуятб п и полагаем b =
2 3' 3 2
у -х -ах (mod п). (Если при этом НОД (4а +276 , п) > 1, то выбираем другую тройку (а,х,у). — Прим. перев.) Тогда P = (х,у) есть эле-
2 3
мент множества Е, которое определяется уравнением у = х + ах + Ь. Используем метод Шуфа (или другой метод для подсчета числа точек на эллиптической кривой), чтобы найти число т, которое при простом п равно числу точек эллиптической кривой E над Fn. Если мы не можем представить т в виде т = kq, где k ^ 2 — малое целое число, a q - «вероятно простое» (т. е. прошедшее один из тестов § V. 1), то выбираем другую случайную тройку (а,х,у) и повторяем действия с начала. Предположим, что мы получили, наконец, эллиптическую кривую, для которой т имеет искомый вид. Тогда с помощью формул из § VI. 1 (работая по модулю п) находим тР и кР. Если мы в какой-то момент получаем неопределенное выражение — либо при нахождении кратной для точки Р, либо при использовании алгоритма Шуфа, то мы сразу находим нетривиальный делитель числа п. Мы можем предположить, что этого не случается. Если тР ф О, то п — составное (так как, если бы п было простым, группа E имела бы порядок т и
§ 3. КРИТЕРИЙ ПРОСТОТЫ
215
любой элемент E при умножении на т обращался бы в нуль). Если кР = О (что весьма маловероятно), то нам не повезло и нужно начинать заново с другой тройкой. Но если тР = О и кP ф О, то согласно предложению VI. 3. 2 число п — простое, если большой делитель q числа т — действительно простое число (а мы знаем только, что q — «вероятно простое»). Это сводит задачу к доказательству простоты числа q, которое не превосходит п/2. Мы затем начинаем снова с q вместо п. Таким образом, мы получаем рекуррентную процедуру с t применениями критерия простоты, где t не больше log2 п. В конце работы мы получаем число qt, о котором знаем, что оно простое; отсюда следует, что предыдущее qt-\ было на самом деле простым (а
