А.В. Рожков, О.В. Ниссенбаум - Теоретико-числовые методы в криптографии (1127102), страница 21
Текст из файла (страница 21)
Поскольку 17 mod 4 = 1, то наложение решета S4 начнем с S4(1),
17 mod 5 = 2, то наложение решета S5 начнем с S5(2),
17 mod 7 = 3, то наложение решета S7 начнем с S7(3).
| x | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 |
| S4 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| S5 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 |
| S7 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
Среди чисел от 17 до 34 остались 20, 22, 28,
Проверим их:
x=20, x2=400, z=x2—n=121, y= 
=11, y2=121=z.
Тогда a=x+y=31, b=x—y=9.
Ответ: 279=31·9.
2.4. Ро-метод Полларда.
Ро-метод Полларда – метод специального назначения для поиска малых делителей.
Пусть n – число, которое требуется факторизовать, и f(x) – случайный полином над Zn. Возьмем x0 – случайное число из Zn и построим последовательность x1, x2,…., xk, … по правилу xi+1=f(xi), i=0, 1, …. Поскольку Zn – конечное множество, то рано или поздно в последовательности возникнет xs+i=xi, s<n. То есть последовательность x1, x2,… войдет в цикл периодом s.
Замечание: среднее ожидаемое величины периода последовательности, построенной выше, есть E(s)=
.
Пусть p – простой делитель числа n, и в последовательности, построенной выше, нашлись числа xi, xj: xi≡xj (mod p), xi
xj (mod n).
Тогда p\НОД(xi—xj,n), n не делит НОД(xi—xj,n), а значит НОД(xi—xj,n) является нетривиальным делителем n.
Ро-метод Флойда использует функцию f(x)=x2+1 mod n, а для поиска чисел xi, xj применяет метод Флойда поиска периода последовательности.
Метод Флойда поиска периода последовательности:
Вычисляем x2=f(x1). По паре (x1, x2) вычисляем пару (x2=f(x1), x4=f(f(x2))) и т. д., по паре (xi, x2i) вычисляем пару (xi+1=f(xi), x2(i+1)=f(f(x2i))). Как только получаем пару одинаковых значений xm=x2m, заключаем, что m\s, где s – период последовательности. Кроме того, если l – длина предпериода последовательности (то есть количество первых членов последовательности, пока та не вошла в цикл), то m=s
.
Этот метод позволяет сэкономить память для последовательностей большого периода. Действительно, одновременно следует хранить лишь два члена последовательности. Если бы поиск периода велся традиционным способом (последовательного вычисления всех членов последовательности до первого повторения), то потребовалось бы место для хранения l+s членов.
Алгоритм Ро-метода Полларда для факторизации.
Вход: n – составное число.
f(x)=x2+1 mod n.
Ш.1. x1=2, x2=2.
Ш.2. Вычислить x1=f(x1), x2=f(f(x2)).
Ш.3. Если x1=x2, то выбрать другой полином (например, f(x)=Ax2+C mod n (A, C - константы)) и снова начать алгоритм с Шага 1.
Ш.4. Вычислить d=НОД(x1—x2, n).
Ш.5. Если d=1, то вернуться на Шаг 2.
Выход: d\n.
Пример:
n=533.
| x1 | 2 | 5 | 26 | 144 | 483 |
| x2 | 2 | 26 | 483 | 247 | 210 |
| abs(x1—x2) | - | 21 | 457 | 103 | 273 |
| d | - | 1 | 1 | 1 | 13 |
Нашли нетривиальный делитель числа n: d=13.
Ответ: 533=13·41.
Замечание: Если f(x) генерирует псевдослучайную последовательность (а это так, если f(x)=Ax2+C mod n и A, B, n – попарно простые числа, то f(x) – линейный конгруэнтный генератор), то сложность данного метода составляет О(
) модулярных умножений.
Ро-метод Полларда может быть применен и для факторизации на конечном множеством многочленов.
2.5. p—1 – метод Полларда.
Данный метод является методом специального назначения для нахождения р - простого делителя составного числа n, для которого p—1 есть B-гладкое число.
Число a называется B-гладким, если все его простые делители не превышают B.
Идея метода заключается в следующем: зададим целое число B≤
. Возьмем какое-нибудь простое число q≤B и возведем его в такую максимально возможную целочисленную степень, чтобы результат не превышал n. Очевидно, показатель этой степени будет 
. Зададим число Q следующим образом:
Q=
.
Если p – простой делитель числа n, для которого p—1 является B-гладким, то (p—1)\Q. Согласно теореме Ферма, для всех a: НОД(a,p)=1 выполняется aQ≡1(mod p). Поэтому если d=НОД(aQ—1,n)≠n, то d – нетривиальный делитель n. Если же d=n, то метод дает отказ.
Граница B выбирается исходя из вычислительных возможностей и априорных сведений о факторизуемом числе. На практике часто выбирают B между 105 и 106.
Алгоритм p—1 – метода Полларда:
Вход: n – нечетное составное число, не являющейся степенью целого числа.
Ш.1. Выбрать границу B. Составить таблицу простых чисел, меньших или равных B (если такой таблицы не имеется).
Ш.2. Выбрать случайное число a: 1<a<n. Вычислить d=НОД(a,n). Если d>1, то идти на Выход.
Ш.3. Для каждого простого q≤B вычислить l=
и a=a·ql mod n.
Ш.4. Вычислить d=НОД(a—1,n).
Ш.5. Если d=1 или d=n, то отказ.
Выход: d – нетривиальный делитель n.
Пример.
n=5945.
Ш.1. В=10. Простые числа, меньшие 10: 2, 3, 5, 7.
Ш.2. а=17. НОД(17,5945)=1.
Ш.3.
| q | 2 | 3 | 5 | 7 |
| l | 12 | 7 | 5 | 4 |
| ql mod n | 4096 | 2187 | 3125 | 2041 |
| a | 4096 | 4782 | 3965 | 2020 |
a=2020.
Ш.4. d=НОД(2020, 5945)=5.
Ответ: 5945=5·1189.
Замечание: Сложность данного алгоритма составляет O
умножений по модулю.
2.6. Методы случайных квадратов.
Пусть n – нечетное составное число, не являющееся степенью целого числа. Методы случайных квадратов – это группа методов, основанная на следующей идее:
Пусть n – нечетное составное число, не являющееся степенью целого числа. Целые x, y – такие случайные числа, что x2≡y2(mod n), x ±y(mod n). Тогда n\(x2—y2), но n не делит ни (x+y), ни (x—y), а значит НОД(x—y,n) – нетривиальный делитель n.
Методы случайных квадратов ищут случайным образом числа x, y: x2≡y2(mod n), а затем проверяют, что x ±y(mod n).
Замечание: Если x, y – случайные числа, такие что x2≡y2(mod n), то P(x ±y(mod n)) ≤ 1/2. Действительно, сравнение a≡x2(mod n) имеет 2k различных корней, если n имеет k различных простых делителей, 2k—2 из которых подходят к вероятности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
