Пусть p — делитель числа m. Рассмотрим элементы последовательности (2) по модулю p (т.е. образы элементов bi при каноническом эпиморфизмеZm → Zp): c0 == b0(mod p), c1 == b1(mod p), c2 == b2(mod p), … (3) Так как в Zp меньше элементов, чем в Zm, то с большой вероятностью период последовательности (3) меньше, чем период последовательности (2). Следовательно, найдется пара индексов i, j такая, что ci = cj, bi ≠ bj. Это означает, что bi == bj (modp), bi ≠ bj (modm).
Отсюда вытекает, что (bi — bj) делится на p, но не делится на m. Следовательно, НОД (bi — bj, m) нетривиален, и нам удалось разложить m на множители. Итак, алгоритм Полларда 1 сводится к поиску цикла в бесконечной рекурсивной последовательности, состоящей из элементов конечного множества. При этом вместо того, чтобы сравнивать между собой два элемента, мы вычисляем наибольший общий делитель их разности и числа m. Алгоритм завершается, когда наибольший общий делитель нетривиален. Можно предложить 2 способа решения задачи поиска цикла в последовательности. Первый способ наиболее простой.
Второй чуть-чуть сложнее, но зато более быстрый. Способ 1 Выполняется следующая последовательность сравнений: b0 ↔ b1b1 ↔ b3b2 ↔ b5b3 ↔ b7b4 ↔ b9... bi ↔ b2i+1... Рано или поздно мы дойдем до равенства двух элементов, поскольку расстояние между сравниваемыми элементами на каждом шаге увеличивается ровно на единицу; кроме того, левый элемент сдвигается вправо, так что он рано или поздно войдет в периодический участок последовательности.
Выпишем алгоритм нахождения делителя. алгоритм факторизация1(вход: целое число m, — выход: целое число d): успехдано: целое число mнадо: получить нетривиальный делитель d числа mвозвращаемое значение: true, если удалось разложить, — false в противном случаеначалоmaxSteps := 1 000 000 // Максимальное число шаговstep := 0— b0 := случайное число в интервале 0. mb1 := mod (b0 * b0 + 1, m) — d := gcd (b1 — b0, m) — циклпока step < maxSteps && d == 1 // Пока
НОДтривиален- -выполнять- - b0 = mod (b0 * b0 + 1, m) // Применяем отображение f- - b1 = mod (b1 * b1 + 1, m); // один раз к b0 и дважды- - b1 = mod (b1 * b1 + 1, m) // к b1- - d := gcd (b1 — b0, m) — - step := step + 1- конец_цикла— вернуть (d ≠ 1) // Успех := d нетривиаленконец_алгоритма
На каждом шаге цикла мы трижды вычисляем значение отображения f. Небольшая модификация алгоритма позволяет делать это только один раз. Способ 2 Выполняется следующая бесконечная последовательность сравнений b0 ↔ b1b1 ↔ b2b1 ↔ b3b2 ↔ b4b2 ↔ b5b2 ↔ b6b2 ↔ b7b4 ↔ b8b4 ↔ b9b4 ↔ b10... b4 ↔ b15b8 ↔ b16b8 ↔ b17... b8 ↔ b31.
.. Вся последовательность сравнений разбивается на серии. В очередной серии мы сравниваем элемент bs, где s — степень двойки, последовательно с элементами b2s, b2s+1, b2s+2, …, b4s-1. Серия содержит 2s сравнений. Выпишем алгоритм. алгоритм факторизация2(вход: целое число m, — выход: целое число d): успехдано: целое число mнадо: получить нетривиальный делитель d числа mвозвращаемое значение: true, если удалось разложить, — false в противном случаеначалоmaxSteps := 19 // Максимальная длина серии 219- step := 0— b0 := случайное число в интервале 0. mb1 := mod (b0 * b0 + 1, m) — a := b1 // Первый элемент серииseriesLength := 1 // Длина серииd := gcd (b1 — b0, m) — цикл пока step < maxSteps && d == 1 // пока НОД тривиален- - выполнять- - Инвариант: — - b0 — элемент последовательности с индексом, — - равным нулю или степени двойки- - a — элемент, индекс которого равен удвоенному индексу- - элемента b0 (или 1, если индекс b0 равен 0) — - seriesLength == удвоенному индексу элемента a- - d := gcd (b1 — b0, m) — - len := 0- — - циклпока d == 1 иlen < seriesLength- - - выполнять- - - b1 = mod (b1 * b1 + 1, m);
— - - d := gcd (b1 — b0, m) — - - len := len + 1- - конец_цикла- — - b0 := a- - a := b1- - seriesLength := seriesLength * 2- конец_цикла— вернуть (d ≠ 1) // Успех := d нетривиаленконец_алгоритма
Метод Монте-Карло 2: (p-1)-алгоритм Полларда
Пусть m — целое число, которое мы раскладываем на множители. Оно представимо в виде произведения степеней простых чисел m = p1e1p2e2 … pkekПредположим, что p1−1 представимо в виде произведения степеней простых чисел, причем каждая из этих степеней не очень велика. Более точно, существует N такое, что p1−1 = q1a1q2a2 … qrar, q1a1 < N, q2a2 < N, …, qrar < N.
Рассмотрим всевозможные максимальные степени простых чисел, не превосходящие N. Например, пусть N = 20, тогда рассматриваются степени простых 16, 9, 5, 7, 11, 13, 17, 19. Обозначим эти степени простых через t1, t2, …, ts. Выберем произвольное целое число b. Рассмотрим последовательность b0 = b, b1 = b0t1 (mod m), b2 = b1t2 (mod m), …, bs = bs-1ts (mod m) Каждый раз, вычислив bi, вычисляем одновременно НОД (bi — 1, m).
Утверждается, что с большой вероятностью на каком-то шаге этот НОД будет нетривиальным делителем N. Действительно, покажем, что p — НОД (bs — 1, m). Действительно, bs = bt1t2 … tsи, поскольку по предположению, p1 — 1 — t1t2 … ts, то есть t1t2 … ts = (p1 — 1) g, то bs = bt1t2 … ts = b (p1 — 1) g = (b (p1 — 1))g == 1 (mod p1) по малой теореме Ферма.
Значит, bs — 1 делится на p1, число m также делится на p1, следовательно, НОД (bs — 1, m) делится на p1. Проиллюстрируем алгоритм на простом примере. Возьмем N = 20. Выпишем все степени простых, не превосходящие 20: t1 = 16, t2 = 9, t3 = 5, t4 = 7, t5 = 11, t6 = 13, t7 = 17, t8 = 19. Попытаемся разложить на множители число m = 41 779 = 41· 1019
Выберем b = 2. Последовательно вычисляем 216 (mod 41 779) == 23 757, gcd (23 757 — 1, 41 779) = 1,237 579 (mod 41 779) == 7970, gcd (7970 — 1, 41 779) = 1,79 705 (mod 41 779) == 33 580, gcd (33 580 — 1, 41 779) = 41. Мы получили нетривиальный делитель на третьем шаге, поскольку 41−1 = 8· 5 делит (t1t2t3) = 16· 9·5. Заключение
В связи со схемой RSA возникает ряд алгоритмических задач. 1. Для генерации ключей нам надо уметь генерировать большие простые числа. Близкой задачей является проверка простоты целого числа. 2. Для взламывания ключа в RSA нужно уметь раскладывать целое число на множители (или, что практически то же самое, уметь вычислять функцию Эйлера). Взлом ключа может интересовать только преступников, но, с другой стороны, те, кто пытаются защитить информацию, должны быть уверены, что задача разложения на множители достаточно сложна.
Список литературы
Rivest R. L., S hamir A., Adleman L. A method for obtaining digital signatures and public-key cryptosystems (англ.) // Communications of the ACM. — N ew York, NY, USA: ACM, 1978. —
Т. 21. — № 2, Feb.
1978. — С. 120—126. — ISSN
0001−0782. — DOI:
10.1.
1.40. 5588Menezes A., P. van Oorschot, S. V anstone.
H andbook of Applied Cryptography. — CRC-P ress, 1996.
— 816 p. — (D iscrete Mathematics and Its Applications). — ISBN 0−8493−8523−7Венбо
Мао.Современнаякриптография. Теорияипрактика = Modern Cryptography: Theory and Practice. — М.: Вильямс, 2005. —
768 с. — 2000 экз. — ISBN 5−8459−0847−7, ISBN 0−13−66 943−1Фергюсон Н, Б. Шнайер. Практическаякриптография = Practical Cryptography: Designing and Implementing Secure Cryptographic Systems.
— М.: Диалектика, 2004. — 432 с. —
3000 экз. — ISBN 5−8459−0733−0, ISBN 0−4712−2357−3Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = AppliedCryptography. P
rotocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с.
— 3000 экз. — ISBN 5−89 392−055−4
