Метод квадратичного решета.

Пусть n – число, которое надо факторизовать. Как и метод Ферма, данный метод ищет целые числа x, y: n=x²—y², но подход к поиску несколько иной. Поиск числа x осуществляется не среди всех чисел подходящего размера. Перед началом перебора производится отсев некоторых чисел.

Принцип отсева вытекает из следующих рассуждений: Возьмем небольшое число m и рассмотрим полную систему вычетов Z_m={0, 1, 2, … ,m—1}. Среди чисел из Z_m некоторые числа являются квадратами (то есть квадратичными вычетами), а другие не являются. Если m – простое число, то квадратов столько же, сколько неквадратов. Если m – составное, то квадратов несколько меньше. В общем случае,

P(s Q(m)) ≤ .

Если число не является квадратичным вычетом по какому-то модулю m, то оно не является квадратом в Z, поэтому число y² следует искать среди тех чисел, которые являются квадратами в Z_m.

В методе квадратичного решета берут несколько небольших попарно простых модулей m₁, m₂, … , m_k. Для каждого такого модуля составляют квадратичное решето (двоичный вектор S_m) следующим образом:

Для каждого x Z_m вычисляют x² mod m и z=(x²—n) mod m. Если z является квадратом по модулю m, то S_m(x)=1, иначе S_m(x)=0. Проверка того, является ли z квадратом по модулю m, производится путем сверки с вычисленными x² mod m.

После того, как все решёта построены, начинается отсев кандидатов x. Решёта накладываются на последовательность чисел x от +1 до . Те числа, на которые наложился «0» хотя бы одного решета, отсеиваются. После отсева остается достаточно небольшое количество чисел – кандидатов в x. Для каждого такого числа вычисляется x², z= x²–n и y= . Если y²=z, то числа a=x+y, b=x—y являются делителями числа n.

Пример:

n=279.

Построим решёта по модулям 4, 5 и 7:

Теперь, когда мы построили три решета, наложим их на последовательность чисел от +1=17 до =140.

Поскольку 17 mod 4 = 1, то наложение решета S₄ начнем с S₄(1),

17 mod 5 = 2, то наложение решета S₅ начнем с S₅(2),

17 mod 7 = 3, то наложение решета S₇ начнем с S₇(3).

Среди чисел от 17 до 34 остались 20, 22, 28,

Проверим их:

x=20, x²=400, z=x²—n=121, y= =11, y²=121=z.

Тогда a=x+y=31, b=x—y=9.

Ответ: 279=31·9.

Ро-метод Полларда.

Ро-метод Полларда – метод специального назначения для поиска малых делителей.

Пусть n – число, которое требуется факторизовать, и f(x) – случайный полином над Z_n. Возьмем x₀ – случайное число из Z_n и построим последовательность x₁, x₂,…., x_k, … по правилу x_i+1=f(x_i), i=0, 1, …. Поскольку Z_n – конечное множество, то рано или поздно в последовательности возникнет x_s+i=x_i, s<n. То есть последовательность x₁, x₂,… войдет в цикл периодом s.

Замечание: среднее ожидаемое величины периода последовательности, построенной выше, есть E(s)= .

Пусть p – простой делитель числа n, и в последовательности, построенной выше, нашлись числа x_i, x_j: x_i≡x_j (mod p), x_i x_j (mod n).

Тогда p\НОД(x_i—x_j,n), n не делит НОД(x_i—x_j,n), а значит НОД(x_i—x_j,n) является нетривиальным делителем n.

Ро-метод Флойда использует функцию f(x)=x²+1 mod n, а для поиска чисел x_i, x_j применяет метод Флойда поиска периода последовательности.

Метод Флойда поиска периода последовательности:

Вычисляем x₂=f(x₁). По паре (x₁, x₂) вычисляем пару (x₂=f(x₁), x₄=f(f(x₂))) и т. д., по паре (x_i, x_2i) вычисляем пару (x_i+1=f(x_i), x_2(i+1)=f(f(x_2i))). Как только получаем пару одинаковых значений x_m=x_2m, заключаем, что m\s, где s – период последовательности. Кроме того, если l – длина предпериода последовательности (то есть количество первых членов последовательности, пока та не вошла в цикл), то m=s .

Этот метод позволяет сэкономить память для последовательностей большого периода. Действительно, одновременно следует хранить лишь два члена последовательности. Если бы поиск периода велся традиционным способом (последовательного вычисления всех членов последовательности до первого повторения), то потребовалось бы место для хранения l+s членов.

Алгоритм Ро-метода Полларда для факторизации.

Вход: n – составное число.

f(x)=x²+1 mod n.

Ш.1. x₁=2, x₂=2.

Ш.2. Вычислить x₁=f(x₁), x₂=f(f(x₂)).

Ш.3. Если x₁=x₂, то выбрать другой полином (например, f(x)=Ax²+C mod n (A, C - константы)) и снова начать алгоритм с Шага 1.

Ш.4. Вычислить d=НОД(x₁—x₂, n).

Ш.5. Если d=1, то вернуться на Шаг 2.

Выход: d\n.

Пример:

n=533.

Нашли нетривиальный делитель числа n: d=13.

Ответ: 533=13·41.

Замечание: Если f(x) генерирует псевдослучайную последовательность (а это так, если f(x)=Ax²+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 выполняется a^Q≡1(mod p). Поэтому если d=НОД(a^Q—1,n)≠n, то d – нетривиальный делитель n. Если же d=n, то метод дает отказ.

Граница B выбирается исходя из вычислительных возможностей и априорных сведений о факторизуемом числе. На практике часто выбирают B между 10⁵ и 10⁶.

Алгоритм p—1 – метода Полларда:

Вход: n – нечетное составное число, не являющейся степенью целого числа.

Ш.1. Выбрать границу B. Составить таблицу простых чисел, меньших или равных B (если такой таблицы не имеется).

Ш.2. Выбрать случайное число a: 1<a<n. Вычислить d=НОД(a,n). Если d>1, то идти на Выход.

Ш.3. Для каждого простого q≤B вычислить l= и a=a·q^l 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.

a=2020.

Ш.4. d=НОД(2020, 5945)=5.

Ответ: 5945=5·1189.

Замечание: Сложность данного алгоритма составляет O умножений по модулю.