Метод факторизации Диксона

В чисел теории метод факторизации Диксона (также метод случайных квадратов Диксона) или алгоритм Диксона общего назначения факторизации целых чисел ) — алгоритм ; это прототип метода факторной базы . В отличие от других методов факторной базы, его оценка времени выполнения сопровождается строгим доказательством, которое не опирается на предположения о свойствах гладкости значений, принимаемых полиномом.

Алгоритм был разработан Джоном Д. Диксоном , математиком из Карлтонского университета , и опубликован в 1981 году.

Основная идея

Метод Диксона основан на нахождении сравнения квадратов по модулю целого числа N, которое предназначено для факторизации. Метод факторизации Ферма находит такое соответствие, выбирая случайные или псевдослучайные значения x и надеясь, что целое число x ² mod N — идеальный квадрат (в целых числах):

$x^{2}\equiv y^{2}\quad ({\hbox{mod }}N),\qquad x\not \equiv \pm y\quad ({\hbox{mod }}N).$

Например, если N = 84923 (начав с 292, первого числа, большего √ N , и считая вверх), 505 ² mod 84923 равно 256, квадрату 16. Итак (505 − 16)(505 + 16) = 0 mod 84923 . Вычисление наибольшего общего делителя 505 - 16 и N с использованием алгоритма Евклида дает 163, что является коэффициентом N .

На практике выбор случайных значений x займет непрактично много времени, чтобы найти соответствие квадратов, поскольку существует только √ N квадратов меньше N .

Метод Диксона заменяет условие «является квадратом целого числа» на гораздо более слабое условие «имеет только небольшие простые множители»; например, 292 квадрата меньше 84923; 662 числа меньше 84923, простые делители которых равны всего 2,3,5 или 7; и 4767, все простые делители которых меньше 30. (Такие числа называются B-гладкими относительно некоторой границы B .)

Если чисел много $a_{1}\ldots a_{n}$ квадраты которого можно факторизовать как $a_{i}^{2}\mod N=\prod _{j=1}^{m}b_{j}^{e_{ij}}$ за фиксированный набор $b_{1}\ldots b_{m}$ малых простых чисел, линейная алгебра по модулю 2 на матрице $e_{ij}$ даст подмножество $a_{i}$ чьи квадраты объединяются в произведение маленьких простых чисел в четную степень, то есть подмножество $a_{i}$ квадраты которого умножаются на квадрат (надеюсь, другого) числа по модулю N.

Метод

Предположим, что составное число N факторизуется. граница B Выбирается и определяется факторная база называется P ), набор всех простых чисел, меньших или равных B. ( которая Далее целые положительные числа z ищутся такие, что z ² mod N является B -гладким. Поэтому мы можем написать для подходящих показателей a _i ,

$z^{2}{\text{ mod }}N=\prod _{p_{i}\in P}p_{i}^{a_{i}}$

Когда создано достаточное количество этих отношений (обычно достаточно, чтобы число отношений было на несколько раз больше размера P ), методы линейной алгебры , такие как метод исключения Гаусса , можно использовать для перемножения этих различных отношений в таким образом, чтобы все показатели простых чисел в правой части были четными:

${z_{1}^{2}z_{2}^{2}\cdots z_{k}^{2}\equiv \prod _{p_{i}\in P}p_{i}^{a_{i,1}+a_{i,2}+\cdots +a_{i,k}}\ {\pmod {N}}\quad ({\text{where }}a_{i,1}+a_{i,2}+\cdots +a_{i,k}\equiv 0{\pmod {2}})}$

Это дает сравнение квадратов вида a ² ≡ б ² (mod N ), который можно превратить в факторизацию N , N = НОД ( a + b , N ) × ( N /НОД( a + b , N )). Эта факторизация может оказаться тривиальной (т. е. N = N × 1 ), что может произойти только в том случае, если a ≡ ± b (mod N ), и в этом случае необходимо сделать еще одну попытку с другой комбинацией отношений; но если достигается нетривиальная пара множителей N , алгоритм завершается.

Псевдокод

input: positive integer ${\textstyle N}$
output: non-trivial factor of ${\textstyle N}$

Choose bound ${\textstyle B}$
Let ${\textstyle P:=\{p_{1},p_{2},\ldots ,p_{k}\}}$ be all primes ${\textstyle \leq B}$

repeat
    for ${\textstyle i=1}$ to ${\textstyle k+1}$ do
        Choose ${\textstyle 0<z_{i}<N}$ such that ${\textstyle z_{i}^{2}{\text{ mod }}N}$ is ${\textstyle B}$-smooth
        Let ${\textstyle a_{i}:=\{a_{i1},a_{i2},\ldots ,a_{ik}\}}$ such that ${\textstyle z_{i}^{2}{\text{ mod }}N=\prod _{p_{j}\in P}p_{j}^{a_{ij}}}$
    end for

    Find non-empty ${\textstyle T\subseteq \{1,2,\ldots ,k+1\}}$ such that ${\textstyle \sum _{i\in T}a_{i}\equiv {\vec {0}}{\pmod {2}}}$
    Let ${\textstyle x:=\left(\prod _{i\in T}z_{i}\right){\text{ mod }}N}$
        ${\textstyle y:=\left(\prod _{p_{j}\in P}p_{j}^{\left(\sum _{i\in T}a_{ij}\right)/2}\right){\text{ mod }}N}$
while ${\textstyle x\equiv \pm y{\pmod {N}}}$ 

return ${\textstyle \gcd(x+y,N)}$

Пример

В этом примере будет предпринята попытка факторизовать N = 84923, используя границу B = 7. базой фактора Тогда будет P = {2, 3, 5, 7}. Можно осуществлять поиск целых чисел между $\left\lceil {\sqrt {84923}}\right\rceil =292$ и N, квадраты которого по модулю N являются B -гладкими . Предположим, что два из найденных чисел — 513 и 537:

$513^{2}\mod 84923=8400=2^{4}\cdot 3\cdot 5^{2}\cdot 7$

$537^{2}\mod 84923=33600=2^{6}\cdot 3\cdot 5^{2}\cdot 7$

Так

$(513\cdot 537)^{2}\mod 84923=2^{10}\cdot 3^{2}\cdot 5^{4}\cdot 7^{2}\mod 84923$

Затем

${\begin{aligned}&{}(513\cdot 537)^{2}\mod 84923\\&=(275481)^{2}\mod 84923\\&=(84923\cdot 3+20712)^{2}\mod 84923\\&=(84923\cdot 3)^{2}+2\cdot (84923\cdot 3\cdot 20712)+20712^{2}\mod 84923\\&=0+0+20712^{2}\mod 84923\end{aligned}}$

То есть, $20712^{2}\mod 84923=(2^{5}\cdot 3\cdot 5^{2}\cdot 7)^{2}\mod 84923=16800^{2}\mod 84923.$

Полученная факторизация равна 84923 = НОД(20712 - 16800, 84923) × НОД(20712 + 16800, 84923) = 163 × 521.

Оптимизации

Квадратичное решето — это оптимизация метода Диксона. Он выбирает значения x, близкие к квадратному корню из N, такие, что x ² по модулю N невелик, что значительно увеличивает вероятность получения гладкого числа.

Другие способы оптимизации метода Диксона включают использование лучшего алгоритма для решения матричного уравнения, используя преимущества разреженности матрицы: число z не может иметь больше, чем $\log _{2}z$ коэффициенты, поэтому каждая строка матрицы почти полностью состоит из нулей. На практике блочный алгоритм Ланцоша часто используется . Кроме того, размер факторной базы необходимо выбирать осторожно: если она слишком мала, будет трудно найти числа, которые полностью факторизуются по ней, а если она слишком велика, придется собирать больше отношений.

Более сложный анализ, использующий приближение, согласно которому все простые делители числа меньше $N^{1/a}$ с вероятностью около $a^{-a}$ (аппроксимация функции Дикмана-де Брюйна ), указывает на то, что выбор слишком маленькой факторной базы намного хуже, чем слишком большой, и что идеальный размер факторной базы равен некоторой степени $\exp \left({\sqrt {\log N\log \log N}}\right)$.

Оптимальная сложность метода Диксона равна

$O\left(\exp \left(2{\sqrt {2}}{\sqrt {\log n\log \log n}}\right)\right)$

в обозначении big-O , или

$L_{n}[1/2,2{\sqrt {2}}]$

в L-нотации .