Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
вида 0(еС^г 1о§ г), где г — число бит в п. Подробный вывод оценки времени работы можно найти в статье Ленстры.
Точнее, предположим, что п — натуральное число, которое не есть степень простого и не делится на 2 и на 3. Используя правдоподобное предположение о распределении целых чисел, не делящихся на простые числа, большие В, в малом интервале вокруг р, Ленстра доказывает следующую вероятностную временную оценку для числа двоичных операций, требующихся для получения нетривиального делителя п:
е\/(2 + ?) logplog logp
где р — наименьший простой делитель п и є сколь угодно близко к нулю для достаточно больших р. Так как всегда р < у/п, из (3) получается также оценка
e\/(l + e) lognloglogn ^
Оценка (4) имеет тот же самый вид, что и (эвристические) временные оценки для лучших из известных общих методов факторизации. Однако метод Ленстры имеет следующий ряд преимуществ перед своими конкурентами.
1. Это — единственный метод, время работы которого существенно уменьшается, если п делится на простое число, значительно меньшее у/п.
2. По этой причине его можно использовать в сочетании с другими методами факторизации, когда требуется разлагать на множители какие-либо вспомогательные числа. (Например, в методе цепных дро-бей из § V. 4 нам нужно полное разложение числа bi (mod п), если оно есть произведение относительно малых простых чисел.)
3. В отличие от своих конкурентов он использует небольшой объем памяти.
Однако самой замечательной особенностью факторизационного алгоритма Ленстры является исторически первое использование эллиптических кривых — интенсивно изучаемого объекта современной теории чисел и алгебраической геометрии, обладающего богатой структурой. Это показывает возможность появления новых методов раз-
226
ГЛ. VI. ЭЛЛИПТИЧЕСКИЕ КРИВЫЕ
ложения на множители, использующих неожиданные построения из доселе весьма далеких областей математики.
УПРАЖНЕНИЯ
1. Используя метод Полларда с к = 840 и а = 2, попытаться разложить на множители п = 53467. Затем сделать попытку с а = 3.
2. Предположим, что лишь один из простых делителей р числа п таков, что р — 1 не делится на большие простые числа. Предположим, что в алгоритме Полларда берется значение к, которое не кратно р — 1, и пробуются различные значения а. Оцените в терминах к и р — 1 вероятность получить d = р на шаге 4.
3. Для следующих значений р и В найти (используя, если необходимо, компьютер) долю целых чисел между р + 1 — 2^/р и р + 1 + 2^/р, которые не имеют простых делителей, больших В: а) р = 109, В = 3; б) р = 109, В = 19; в) р = 1009, В = 19; г) р = 1009, В = 97; д) р = 9973, В = 97.
4. Каждое из чисел п в упражнении 5 из §V.4 имеет делитель р < 100. В каждом из случаев а)-л) найти этот делитель методом Ленстры эллиптических кривых, выбирая В = 5, С = 120, P = (1, 1) и Е: у2 = х3-\-ах — а при а = 1,2,... (взяв те а, для которых дискриминант взаимно прост с га). Каково в каждом из случаев первое значение а, для которого вы находите делитель, и каково при этом первое значение к\, для которого найденный делитель появляется как НОД (знаменатель, га) при вычислении к\ Pl
5. Пусть к задано равенством (2). Предположим, что вы находите делитель числа п в процессе вычисления к\Р по модулю га, где к\ — частичное произведение в (2). (Напомним, что мы вычисляем кР, умножая последовательно на числа / в порядке возрастания.) Докажите, что к\ P (mod р) = О (mod р) для некоторого р\п, исключив тем самым возможность получения знаменателя, не взаимно простого с га, при вычислении 1((к\/1)Р) на одном из этапов метода удвоения, предшествующем последнему шагу.
6. а) Предположим, что для любого а Є Z имеется эффективный способ нахождения такой точки P = (х,у), что у2 = х3 + ах (mod га). Объясните, чем плоха идея использовать для разложения п эллиптическую кривую у ~=~^х3 -fei с различными а.
б) Тот же вопрос для семейства эллиптических кривых у2 = X3 + 6 с различными Ь.
7. Предположим, что вы хотите немного увеличить вероятность того, что порядок E (mod р) для некоторого p\N есть произведение малых простых множителей, обеспечивая делимость этого порядка на 4. Опишите, как это сделать.
ЛИТЕРАТУРА к § 4 ГЛАВЫ VI
1. Lenstra Н. W., Jr. Factoring integers with elliptic curves. — Ann. Math., 1987, v. 126, p. 649-673.
2. Montgomery P. Speeding the Pollard and elliptic curves methods of factorization. — Math. Comp., 1987,_v. 48, p. 243-264.
3. Pollard J. M. Theorems on factorization and primality testing. — Proc. Cambridge Phil. Soc, 1974, v. 76, p. 521-528.
ОТВЕТЫ К УПРАЖНЕНИЯМ
§i.i
1. (112111)3.
2. (260^)7.
3. 10001100101; 1101
4. MPJNS; LIKE^ (другими словами, JQVXHJ=WE-LIKE+IT).
5. а) 10.101101111110000. б) С.SRO.
6. Если Ъ! - 1 кратно d, то дробь можно записать в виде а/(Ъ? — 1), где а — целое число не более чем из / разрядов. Теперь воспользуйтесь формулой для суммы геометрической прогрессии с первым членом аЪ~Ї и знаменателем b~*. Обратно, при заданном чисто периодическом разложении х с периодом / покажите, что b-f X отличается от х на /-значное целое а. Это означает, что х = a/(b^ — 1).
