Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
3. Goldwasser S., Kilian J. Almost all primes can be quickly certified. — In: Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986, p. 316-329.
4. Lenstra A. K., Lenstra H. W.,Jr. Algorithms in number theory. — Technical Report 87-008. Chicago: University of Chicago, 1987.
5. Morain F. Implementation of the Goldwasser-Kilian-Atkin primality testing algorithm. — INRIA report 911, 1988.
6. Pocklington H. The determination of the prime and composite nature of large numbers by Fermat's theorem. — Proc. Cambridge Phil. Soc, 1914-16, v. 18, p. 29-30.
7. Schoo] R. Elliptic curves over finite fields and the computation of square roots mod p. — Math. Сотр., 1985, v. 44, p. 483-494.
§ 4. Разложение на множители при помощи эллиптических кривых
Основной причиной повышенного интереса части криптографов к эллиптическим кривым послужило недавно найденное Ленстрой (Н. W. Lenstra) остроумное применение эллиптических кривых в новом методе факторизации, которой во многих отношениях лучше су-ществоваших ранее. С точки зрения практики, это продвижение не настолько значительно, чтобы угрожать надежности криптосистем, основанных на трудности задачи разложения на множители (оценки времени имеют тот же вид, с которым мы уже встречались в § V. 3). Тем не менее, открытие более совершенного метода, использующего неожиданный новый инструментарий, предостерегает от благодушия по поводу невозможности существенных продвижений в задаче разложения на множители. Цель этого последнего параграфа — описание метода Ленстры.
Предваряя изложение алгоритма Ленстры разложения на множители с помощью эллиптических кривых, мы напомним один классический способ факторизации, аналогичный методу Ленстры.
(р - 1)-метод Полларда. Пусть мы хотим разложить на множители составное число п и предполагаем, что р — его (еще не известный) простой делитель. Если р таков, что р — 1 не имеет больших простых делителей, то р можно найти следующим способом.
1. Выбираем целое число к, кратное всем или большинству целых чисел, меньших некоторой границы В. Например, в качестве к можно взять В\ или общее наименьшее кратное всех целых чисел, не превосходящих В.
218
ГЛ. VI. ЭЛЛИПТИЧЕСКИЕ КРИВЫЕ
2. Выбираем целое число а между 2 и п - 2. Например, а может быть равно 2, 3 или случайно выбранному целому числу.
к
3. Вычисляем а по модулю п повторным возведением в квадрат.
4. Вычисляем d = НОД (ак - 1,п), используя алгоритм Евклида и вычет ак (mod п) из шага 3.
5. Если d не есть нетривиальный делитель п, то повторяем все шаги с новым а и/или новым к.
Чтобы понять, при каких условиях этот алгоритм будет работать, предположим, что к делится на все натуральные числа, не превосходящие В. Далее, пусть р — простой делитель п, для которого р — 1 представляется в виде произведения степеней небольших простых чисел, причем каждый из сомножителей меньше В. Отсюда следует, что к кратно р-1 (так как оно кратно каждому из сомножителей в разложении р—1). Поэтому, по малой теореме Ферма, имеем а = 1 (mod р). Тогда НОД (ак — 1, п) делится на р. Таким образом, единственное препятствие, которое может помешать нам получить на шаге 4 нетривиальный делитель п, — это случай, когда ак = 1 (mod п).
Пример 1. Разложим указанным методом n = 540143. Выбираем В = 8 (и, следовательно, к равно 840 — общему наименьшему кратному 1,2,...,8) и а = 2. Находим, что 2840 (mod ті) — это 53047 и НОД (53046, n) = 421. Тем самым приходим к разложению 540143 = 421 • 1283.
Основная слабость метода Полларда, очевидно, проявляется при попытках его применения в тех случаях, когда вч;е простые делители р числа тг таковы, что р—1 делится на относительно большое простое число (или на большую степень простого числа).
Пример 2. Пусть ті = 491389. Вряд ли мы найдем нетривиальный делитель, если выберем В < 191. Причина этому — разложение n = 383 • 1283: мы имеем 383 - 1 = 2 • 191, 1283 - 1 = 2 • 641 (как 191, так и 641 — простые числа). За исключением а = 0, ±1 (mod 383), все другие а имеют порядки по модулю 383 либо 191, либо 382; за исключением a = 0,±1 (mod 1283), все другие значения а имеют порядки по модулю 1283 либо 641, либо 1282. Таким образом, если к не делится на 191 (или 641) то, скорее всего, на шаге 4 мы вновь и вновь будем получать НОД (ак — l,n) = 1.
Основной недостаток (р — 1)-метода Полларда состоит в том, что в нем используется только группа (Z/pZ)* (точнее, различные такие группы, когда р пробегает простые делители п). Для данного п эти группы фиксированны. Если порядок каждой из них делится на большое простое число, метод не работает.
Принципиальное отличие метода Ленстры, как мы увидим, со-
§ 4. РАЗЛОЖЕНИЕ НА МНОЖИТЕЛИ
219
стоит в том, что при использовании эллиптических кривых над полем Fp = Z/pZ мы неожиданно получаем целый сонм групп и поэтому можем рассчитывать найти среди них такую, у которой порядок не делится на большое простое число или большую степень простого числа.
Мы начнем описание алгоритма Ленстры с некоторых комментариев по поводу редукции точек на эллиптических кривых по модулю п, где п — составное число (в отличие от §2, где мы работали по модулю простых чисел и в конечных полях).
