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

Пусть 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 членов.