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

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

История


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

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


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

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