Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
4. Использовать обобщенную факторизацию Ферма, чтобы разложить на множители:
а) 68987; б) 29895581; в) 19578079; г) 17018759.
5. Пусть га = 2701. Использовать 5-числа 522,532 (mod га) (при подходящей факторной базе В), чтобы разложить 2701. Какие векторы ? соответствуют 52 и 537
6. Пусть га = 4633. Использовать 68, 152 и 153 с соответствующей факторной базой В, чтобы разложить 4633. Каковы соответствующие векторы?
7. а) Доказать, что log га! — (га log га — га) = 0(log га).
б) Вывести более точную оценку log га! — ((га + ^) log га — га) = 0(1).
в) Каково математическое ожидание log j для случайно выбранного j в интервале от 1 до yl
8. а) Какова вероятность того, что к случайно выбранных векторов в линейно независимы (при к га)?
б) Какова вероятность того, что 5 случайно выбранных векторов в Fj образуют базис?
9. Пусть га — г-разрядное двоичное целое число. На какой множитель умножается каждое из выражений у/п (которое входит во временную оценку для ро-
метода) и е 1о&т (которое входит во временную оценку для метода факторных баз), когда га возрастает от 50-значного десятичного числа до 100-значного?
10. а) Пусть /(s) — положительная монотонно убывающая функция, a g(s) — положительная монотонно возрастающая функция на некотором интервале. Предположим, что /(so) = g(so)- Доказать, что функция h(s) = /(s) + g(s) «по существу» достигает минимума в точке so в том смысле, что минимальное значение h(s) лежит между h(so) и ^h(so)-
б) Предположим, что /(s) > 1 — монотонно убывающая функция, g(s) > 1 — монотонно возрастающая функция на интервале и /(so) = S(so). Доказать, что h(s) = f(s)g(s) «по существу» достигает минимума в точке So в том смысле, что минимальное значение h(s) лежит между h(so) и y/h(so).
в) Используя часть б), показать, что функция h(s) = (г/s)rI"ек" на интервале (0, г) (здесь к и г — положительные константы) «по существу» достигает своего минимального значения при (гjs)T'<= екз.
ЛИТЕРАТУРА к § 3 ГЛАВЫ V
1. Dickson L. Е. History of the Theory of Numbers. Vol. 1. N.Y.: Chelsea, 1952.
2. Kraitchik M. Theorie des nombers. Vol. 2. Paris-Montrouge: Gauthier-Villars, 1926.
3. Lehman R. S. Factoring large integers. — Math. Сотр., 1974, v. 28, p. 637-646.
4. Pomerance C. Analysis and comparison of some integer factoring algorithms. — Computational Methods in Number Theory. Part I. Amsterdam: Mathematic Centrum, 1982.
174
ГЛ. V. ПРОСТОТА И ФАКТОРИЗАЦИЯ
§ 4. Метод цепных дробей
В последнем параграфе мы видели, что эффективность метода факторных баз для нахождения нетривиального делителя большого составного натурального числа п зависит от наличия хорошего метода получения целых чисел Ь между 1 и ті, для которых наименьший абсолютный вычет b (mod п) разлагается в произведение малых простых чисел. Вероятность такого разложения тем больше, чем меньше значение наименьшего абсолютного вычета b (mod п). В этом параграфе мы опишем метод (восходящий к Лежандру) поиска многих b с тем свойством, что \b2 (mod п)\ < 2у/п. Этот метод использует «цепные дроби». Поэтому мы начнем с краткого введения в теорию представления вещественных чисел в виде цепных дробей. Наше описание коснется лишь свойств, которые потребуются в дальнейшем. Более подробное изложение теории цепных дробей можно найти, например, в классической книге Давенпорта (Davenport), см. ссылки в конце параграфа*.
Цепные дроби. Для вещественного числа х построим его разложение В ВИДЄ ЦеПНОЙ Дроби СЛеДуЮЩИМ ОбраЗОМ. ПуСТЬ Oq = [х] ([х] — наибольшее целое число, не превосходящее х). Положим X0 =
X-CIq; ПуСТЬ O1 = [1 /ж] И х\ = 1/xq — ui J ДЛЯ І > 1 ПОЛОЖИМ Я; = [1/Ж ? _ j ]
и Xi = 1/хг_і — ui. Когда оказывается, что \/хі_\ — целое число, то Xi = 0 и процесс прекращается. Нетрудно понять, что процесс заканчивается в том и только том случае, когда х — рациональное число (потому что в этом случае дроби Xi — рациональные числа с уменьшающимися знаменателями). В силу построения чисел ар, ai,...,а; для каждого і мы можем записать:
1
X = а0 И----,
а-2 +----——-
(Zi -у X і
что обычно записывается в более компактной форме:
111 1 X = ао H----• • •-.
o1+ o2+ o3+ CLi + Xi
Предположим, что X — иррациональное вещественное число. Если мы выполняем описанное разложение до г'-го члена и затем удаляем Xi,
* На русском языке теория цепных дробей излагается в книгах А.Я.Хинчина «Цепные дроби» (M.: ГИФМЛ, 1961), Дж. В. С. Касселса «Введение в теорию дио-фантовых приближений» (M.: ИЛ, 1961) и др. — Прим. ред.
§ 4. МЕТОД ЦЕПНЫХ ДРОБЕЙ
175
то получаем рациональное число bj/cj, называемое г-м приближением цепной дроби х:
bi 111 11
— = а0 +
Ci а1+а2+а3-\- а,-і+ «і
Предложение V. 4.1. В обозначениях, введенных выше, имеем:
a) Ьц = га. bj. = ^a1+! ^ = °.Ь.-!+Ь-2 для і ;> 2;
'c0 1 ' C1 а] ' с, a,c,_i + c,_2 ^ >
b) е п. а) дроби в правых частях — несократимые, т. е. если bi = aibi_1 + Ьг—2 и с,- = а,Сг_! + с,_2, то НОД (bi, с{) = 1;
