Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
3. x2 - 1, x0 = 5, п = 7031.
4. x3 + x + 1, x0 = 1, п = 2701.
5. Пусть множество S состоит из г элементов, а отображение / в паре (/, хо) пробегает все биекции S на себя (т. е. / : S —> S есть взаимно однозначное соответствие S с самим собой, т. е. никакие два разных элемента не имеют одинакового
160
ГЛ. V. ПРОСТОТА И ФАКТОРИЗАЦИЯ
образа при отображении /). Как и прежде, пусть ij + i = f(xj), j = 0,1,... Для каждой пары (/, го) пусть к обозначает первый из таких индексов, для которого найдется j < к со свойством Xj = х^. Доказать, что:
а) к не превосходит г и принимает каждое значение от 1 до г с вероятностью 1 /г;
б) среднее значение для к равно (г + 1)/2 (среднее берется по всем парам (/, хо), где / — биекция).
6. Используя упражнение 5, объяснить, почему в ро-методе в качестве f(x) никогда не следует брать линейный многочлен ах + Ъ.
7. Предположим, что ро-метод используется для разложения числа, имеющего простой делитель г. В качестве функции для итерации решено взять f(x) = х2. (Это плохой выбор, что станет ясно ниже.) Нас интересует первое значение к, при котором ц, = Xj (mod г) для некоторого j < к, т.е. первое значение к, при котором не все го, xl, • ¦ ¦ , хк различны (по модулю г). Предположим, что в качестве Io выбран порождающий элемент группы (Z/rZ)*. Положим г — 1 = 2"t, где t нечетно.
а) Написать сравнение по модулю г — 1, эквивалентное соотношению хц = х\ (равенство обозначает сравнение по модулю г).
б) Найти первые значения киї, для которых выполнено условие из а), выразив ответ в терминах s и двоичного разложения дроби 1/t.
в) Сколь велико должно быть к по сравнению с г? Почему сделанный выбор функции f(x) является плохим для ро-метода?
ЛИТЕРАТУРА к §2 ГЛАВЫ V
1. Blair W.D., Lacampagne СВ., Selfridge J.L. Factoring large numbers on a pocket calculator. — Amer. Math. Monthly, 1986, v. 93, p. 802-808.
2. Brent R. P. An improved Monte Carlo factorization algorithm. — BIT, 1980, v. 20, p. 176-184.
3. Brent R. P., Pollard J. M. Factorization of the eighth Fermat number. — Math. Сотр., 1981, v. 36, p. 627-630.
4. Guy R. K. How to factor a number. — In: Proceedings of the 5th Manitoba Conference on Numerical Mathematics, 1975, p. 49-89.
5. Pollard J. M. A Monte Carlo method for factorization. — BIT, 1975, v. 15, p. 331-334.
§ 3. Факторизация Ферма и факторные базы
Факторизация Ферма. Как мы видели раньше (см. упражнение 3 к § I. 2 и упражнение 4 к § IV. 2), существует способ факторизации составного числа тг, который эффективен, если тг — произведение двух целых чисел, близких одно к другому. Этот метод, называемый «факторизацией Ферма», основывается на том факте, что п в этом случае равно разности двух квадратов, значение одного из которых очень невелико.
§ 3. ФАКТОРИЗАЦИЯ ФЕРМА И ФАКТОРНЫЕ БАЗЫ
161
Предложение V.3.I. Пусть п — натуральное число. Существует взаимно однозначное соответствие между факторизациями п в виде п = ab, где a ^ Ь > 0, и представлениями числа п в виде
2 2
t — s , где sut — неотрицательные целые числа. Это соответствие дается уравнениями:
a + b а — b
: = -, a = t + s, о = t — s.
z 2 '
Доказательство. Если дана такая факторизация, мы пи-
2 2
шем п = ab = ((а + Ь)/2) — ((а - b)/2) , таким образом, мы получаем представление в виде разности двух квадратов. Обратно, если дано
2 2
что п = t — s , мы можем разложить правую часть на множители: (t + s)(t - s). Приведенные в предложении уравнения дают в явном виде взаимно однозначное соответствие между двумя способами представления числа п.
Если п = ab, где а и b близки друг к другу, то s = (a — b)/2 мало, и таким образом, t лишь немного больше у/п. В этом случае мы можем найти а и Ь, пробуя все значения для t, начиная с [у/п\ + 1, пока не
2 2
найдем такое значение, при котором і — п = s есть полный квадрат.
Везде в дальнейшем мы будем предполагать, что п никогда не является полным квадратом; тем самым нам не нужно беспокоиться о тривиальных исключениях в тех или иных процедурах и утверждениях.
Пример 1. Разложить на множители 200819.
гешение. Имеем [\/200819] + 1 = 449. Находим, что 449 — 200819 = 782, и это не есть полный квадрат. Далее, мы пробуем t = 450: 4502 - 200819 = 1681 = 412. Итак, 200819 = 4502 - 412 = (450 + 41)(450- 41) = 491 -409.
Заметим, что если даже а и b в разложении п = ab не близки, то метод факторизации Ферма все равно найдет а и о, но только после большого числа проб для t = [у/п\ + 1, [у/Щ + 2,.. . Существует обобщение метода факторизации Ферма, которое зачастую работает лучше в такой ситуации. Мы выбираем малое к, последовательно полагаем і = [\/fcn] + 1,[VAJn] + 2 и т. д. до тех пор, пока не получим
2 2
такое t, для которого t — кп = s является полным квадратом. Тогда (t 4- s)(t - s) = кп, и, таким образом, t + s имеет с п общий нетривиальный делитель. Он может быть найден путем вычисления НОД (t+s, п).
Пример 2. Разложить на множители 141467.
Решение. Если мы попытаемся использовать факторизацию Ферма, полагая t = 377,378,..., то через некоторое время мы утомимся пробовать различные t. Однако, если мы будем пробовать t = [\/Зп]+1 = 652,..., мы скоро обнаружим, что 655 -3-141467 = 68 ;
