Алгоритм Диксона

Алгоритм Диксона — алгоритм факторизации, использующий в своей основе идею Лежандра, заключающуюся в поиске пары целых чисел x и y таких, что x2y2(modn) и x±y(modn).
 Метод Диксона является обобщением метода Ферма.

История


 В 20-х г. XX столетия Морис Крайчик (1882—1957), обобщая теорему Ферма предложил вместо пар чисел, удовлетворяющих уравнению x2y2=n, искать пары чисел, удовлетворяющих более общему уравнению x2y2(modn). Крайчик заметил несколько полезных для решения фактов. В 1981 г. Джон Диксон опубликовал разработанный им метод факторизации, использующий идеи Крайтчика, и рассчитал его вычислительную сложность.

Описание алгоритма


 Составить факторную базу \Beta={p1,p2,,ph}, состоящую из всех простых чисел p<=M=L(n)12, где L(n)=exp(lnnlnlnn).
 Выбрать случайное $b, \sqrt{n} Вычислить a=b2modn.
 Проверить число a на гладкость пробными делениями. Если a является \Beta-гладким числом, то есть a=p\isin\Betapαp(b), следует запомнить вектора α(b) и ε(b):

α(b)=(αp1(b),,αph(b))
ε(b)=(αp1(b)mod2,,αph(b)mod2).
  Повторять процедуру генерации чисел b до тех пор, пока не будет найдено h+1 \Beta-гладких чисел b1,...,bh+1.
 Методом Гаусса найти линейную зависимость среди векторов ε(b1),,ε(bh+1):

ε(bi1)ε(bit)=0,1tm
  и положить:

x=bi1bitmodn
y=p\isin\Betap(αp(bi1)++αp(bit))2modn.
  Проверить x±y(modn). Если это так, то повторить процедуру генерации. Если нет, то найдено нетривиальное разложение:

n=uv,u=(x+y,n),v=(xy,n).
  \{right)+\{dots+\{alpha\_p\{left(\{b\_\{i\_t\}\}\{right) должна быть четная. Докажем это:

(αp(bi1)++αp(bit))mod2=(εp(bi1)++εp(bit))mod2=ε(bi1)ε(bit)=0
x2y2(modn) следует из того, что:

x2=bi12bit2p\isin\Betapαp(bi1)++αp(bit)(modn)
y2=p\isin\Betapαp(bi1)++αp(bit)
  \}\}

Пример


 Факторизуем число n=89755.

L(89755)=194,174...
M=13,934...
\Beta={2,3,5,7,11,13}
  Все найденные числа b с соответствующими векторами α(b) записываем в таблицу.
baα2(b)α3(b)α5(b)α7(b)α11(b)α13(b)
33723814150200
4305390101210
51996510000
600980201200
670125003000
81739204240020
86021560301210

 Решая линейную систему уравнений получаем, что ε(337)ε(519)=0. Тогда

x=337519mod89755=85148
y=233371mod89755=1512
85148±1512(mod89755)
  Следовательно,

u=(86660,89755)=3095
v=(83636,89755)=29.
  Получилось разложение 89755=309529

Вычислительная сложность


 Обозначим через Ψ(n,M) количество целых чисел a таких, что 1<an и a является \Beta-гладким числом, где \Beta={p:p<M}. Из теоремы де Брёйна — Эрдёша Ψ(n,M)=nuu, где u=lnnlnM. Значит, каждое \Beta-гладкое число будет в среднем попадаться с uu попыток. Для проверки, является ли число \Beta-гладким, необходимо выполнить h делений. По алгоритму необходимо найти h+1 \Beta-гладкое число. Значит, вычислительная сложность поиска чисел

T1=O(uuh2).
  Вычислительная сложность метода Гаусса из h уравнений

T2=O(h3).
  Следовательно, суммарная сложность алгоритма Диксона

T=T1+T2=O(uuh2+h3).
  Учитывая, что количество простых чисел меньше M оценивается формулой h=MlnM, и что u=lnnlnM, после упрощения получаем

T=O(exp(lnnlnlnnlnM+lnM)).
M выбирается таким образом, чтобы T было минимально. Тогда подставляя L(n)=exp(lnnlnlnn), получаем

M=L(n)12
T=O(L(n)2).

Дополнительные стратегии


 Рассмотрим дополнительные стратегии, ускоряющие работу алгоритма.

Стратегия LP


 Стратегия LP использует большие простые числа для ускорения процедуры генерации чисел b.

agraphАлгоритм
 Пусть найденное в пункте 4 число a не является \Beta-гладким. Тогда его можно представить a=sp\isin\Betapαp(b), где s не делится на числа из факторной базы. Очевидно, что s>M. Если дополнительно выполняется s<M2, то s — простое и мы включаем его в факторную базу. Это позволяет найти дополнительные \Beta-гладкие числа, но увеличивает количество необходимых гладких чисел на 1. Для возврата к первоначальной факторной базе после пункта 5 следует сделать следующее. Если найдено только одно число, в разложение которого s входит в нечетной степени, то это число нужно вычеркнуть из списка и вычеркнуть s из факторной базы. Если же, например, таких чисел два b1 и b2, то их нужно вычеркнуть и добавить число b=b1b2. Показатель s войдет в разложение b2modn в четной степени и будет отсутствовать в системе линейных уравнений.

agraphВариация стратегии
 Можно использовать стратегию LP с несколькими простыми числами, не содержащимися в факторной базе. В этом случае для исключения дополнительных простых чисел используется теория графов.

agraphВычислительная сложность
 Теоретическая оценка сложности алгоритма Диксона с применением LP стратегии остается прежней

TLP=O(L(n)2).

Стратегия EAS


 Стратегия EAS (раннего обрыва) исключает некоторые b из рассмотрения, не доводя проверку a на гладкость до конца.

agraphАлгоритм
 Выбираются фиксированные 0<k,l,m<1. В алгоритме Диксона a факторизуется пробными делениями на p<M=L(n)12. В стратегии EAS выбирается M=L(n)k и число сначала факторизуется пробными делениями на p<Ml=L(n)kl, и если после разложения неразложенная часть остается больше, чем n1m, то данное b отбрасывается.

agraphВариация стратегии
 Можно использовать стратегию EAS с несколькими обрывами, то есть при некоторой возрастающей последовательности lj и и убывающей последовательности mj.

agraphВычислительная сложность
 Алгоритм Диксона с применением стратегии EAS при k=27,l=12,m=17 оценивается

TEAS=O(L(n)72).

Стратегия PS


 Стратегия PS использует алгоритм Полларда-Штрассена, который для z,tN и y=z2 находит минимальный простой делитель числа НОД(t,y!) за O(zln2zln2t).

agraphАлгоритм
 Выбирается фиксированное 0<k<1. В алгоритме Диксона a факторизуется пробными делениями на p<M=L(n)12. В стратегии PS выбирается M=L(n)k. Полагаем z=[L(n)k2]+1,y=z2L(n)k,t=a. Применяем алгоритм Полларда-Штрассена, выбирая за t неразложенную часть, получим разложение a.

agraphВычислительная сложность
 Сложность алгоритма Диксона со стратегией PS минимальна при k=13 и равна

TPS=O(L(n)3).