Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
2. а) Предположим, что х — вещественное число, в представлении которого в виде бесконечной цепной дроби
1111
о+ о+ а+ о+
180
ГЛ. V. ПРОСТОТА И ФАКТОРИЗАЦИЯ
бесконечно много раз повторяется натуральное число а. Как записать это вещественное число X в простом виде?
б) Доказать, что при а = 1 в части а) х есть золотое сечение, а числители и знаменатели его приближений суть числа Фибоначчи.
3. Разложить в цепную дробь число є и попытаться угадать схему образования последовательности а,.
4. Объяснить, почему в алгоритме цепных дробей нецелесообразно включать в факторную базу такие простые числа р, что (~) = —1.
5. Следуя примерам 2 и 3, применить алгоритм цепных дробей для разложения на множители следующих чисел: а) 9509; б) 13561; в) 8777; г) 14429; д) 12403; е) 14527; ж) 10123; з) 12449; и) 9353; к) 25511; л) 17873.
1. Davenport Н. The Higher Arithmetic. 5th ed. N.Y.: Cambridge Univ. Press, 1982.
2. Knuth D. The Art of Computer Programming. Vol. 2. Reading: Addison-Wesley, 1973.
3. Lehmer D. H., Powers R. E. On factoring large numbers. — Bull. Amer. Math. Soc, 1931, v. 37, p. 770-776.
4. Morrison M. A., Brillhart J. A method of factoring and the factorization of Ft. — Math. Сотр., 1975, v. 29, p. 183-205.
5. Pomerance C, Wagstaff S.S., Jr. Implementation of the continued fraction integer factoring algorithm. — In: Proceedings of the 12th Winnipeg Conference on Numerical Methods and Computing, 1983.
6. Wunderlich M. С. A running time analysis of Brillhart's continued fraction factoring method. — Lect. Notes Math., (1979, B. 751, S. 328-342.
7. Wunderlich M. С. Implementing the continued fraction factoring algorithm on parallel machines. — Math. Сотр., 1985, v. 44, p. 251-260.
Метод квадратичного решета для факторизации больших целых чисел, разработанный Померанцем в начале 80-х гг., долгое время превосходил другие методы факторизации целых чисел п общего вида, не имеющих простых делителей, порядок величины которых значительно меньше у/п. (Для целых п специального вида могут существовать более быстрые методы с узкой областью применимости, а для чисел п, имеющих простые делители, много меньшие -s/n, более быстрым является метод факторизации на эллиптических кривых, описанный в § VI. 4. См. также обсуждение метода числового решета в конце данного параграфа.)
Квадратичное решето представляет собой вариант метода факторных баз § 3. В качестве факторной базы В мы берем множество простых чисел, состоящее из р = 2 и всех таких нечетных простых
ЛИТЕРАТУРА к §4 ГЛАВЫ V
§ 5. Метод квадратичного решета
§ 5. МЕТОД КВАДРАТИЧНОГО РЕШЕТА
181
чисел р, не превосходящих заданной границы P (выбираемой из соображений оптимальности), что п— квадратичный вычет по модулю р. Множество целых чисел 5, в котором мы ищем Б-числа (напомним, что Б-число — это целое, делящееся только на простые числа из В), — то же самое, что используется при факторизации Ферма (см. §3), а именно:
при надлежаще выбранной границе А.
Основная идея метода состоит в следующем: вместо того, чтобы брать одно за другим каждое s Є 5* и делить его на простые числа из В, чтобы определить, является ли Б-числом число s, мы берем
этой идее. Известное «решето Эратосфена» можно использовать для составления списка всех простых р, не превосходящих А. Например, чтобы составить список простых чисел, не превосходящих 1000, берется список всех целых, не превосходящих 1000, и затем для каждого P = 2,3,5,7,11,13,17,19,23,29,31 из него удаляются все числа, кратные р и большие р; они «проваливаются в отверстия решета, удаленные одно от другого на расстояние р». Оставшиеся числа — простые.
Изложим в общих чертах способ реализации рассматриваемого метода и затем приведем пример. Описанная ниже версия — это лишь один из возможных вариантов метода, и не обязательно самый эффективный. Кроме того, в нашем примере число п, которое нужно разложить (а также соответствующие числа в упражнениях в конце параграфа) взяты из области ss 106, чтобы избежать работы с большими матрицами. Однако такие п слишком малы для того, чтобы продемонстрировать, как решето позволяет экономить время при нахождении большого множества Б-чисёл.
Итак, предположим, что дано нечетное составное число п.
1. Выбираем границы P ж А порядка величины приблизительно
Число А должно быть больше Р, но не превышать сравнительно малой его степени, например, P < А < P .
С функцией ехр{\/log п log log п}, традиционно обозначаемой L(n), мы уже сталкивались в этой главе. Порядок ее роста находится в промежутке между многочленом от logn и многочленом от п. Если п ss 10 , то L(n) ss 400. В примерах, приведенных ниже, выберем
S = {t2 - п I [у/п\ + 1 < * < {,/г!} + А}
\/log Ti log log n
P = 50, A = 500.
182
ГЛ. V. ПРОСТОТА И ФАКТОРИЗАЦИЯ
2. Для і = [у/п\ 4 1, (д/тГ] 4 2,..., [^/п] 4 А выписываем в столбец
.2
по порядку целые числа t — п.
3. Для каждого нечетного простого числа р ^ P проверяем условие (^) = 1 (см. §11.2); если оно не выполняется, то удаляем р из факторной базы.
