Алгоритм Диксона — алгоритм факторизации, использующий в
своей основе идею Лежандра, заключающуюся в поиске пары целых чисел
x
и
y таких, что
x2≡y2(modn) и
x≢±y(modn). Метод Диксона является обобщением метода Ферма.
История
В 20-х г. XX столетия Морис Крайчик (1882—1957), обобщая теорему Ферма
предложил вместо пар чисел, удовлетворяющих уравнению
x2−y2=n,
искать пары чисел, удовлетворяющих более общему уравнению
x2≡y2(modn). Крайчик заметил несколько полезных для решения
фактов. В 1981 г. Джон Диксон опубликовал разработанный им метод
факторизации, использующий идеи Крайтчика, и рассчитал его
вычислительную сложность.
Описание алгоритма
Составить факторную базу
\Beta={p1,p2,…,ph},
состоящую из всех простых чисел
p<=M=L(n)12, где
L(n)=exp(lnn⋅lnlnn−−−−−−−−−√).
Выбрать случайное $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⃗ ,1⩽t⩽m
и положить:
x=bi1…bitmodn
y=∏p\isin\Betap(αp(bi1)+⋯+αp(bit))2modn.
Проверить x≡±y(modn). Если это так, то повторить
процедуру генерации. Если нет, то найдено нетривиальное разложение:
n=u⋅v,u=(x+y,n),v=(x−y,n).
\{right)+\{dots+\{alpha\_p\{left(\{b\_\{i\_t\}\}\{right)
должна быть четная. Докажем это:
(αp(bi1)+⋯+αp(bit))mod2=(εp(bi1)+⋯+εp(bit))mod2=ε(bi1)⊕⋯⊕ε(bit)=0
x2≡y2(modn) следует из того, что:
x2=b2i1…b2it≡∏p\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)
записываем в таблицу.
b | a | α2(b) | α3(b) | α5(b) | α7(b) | α11(b) | α13(b) |
337 | 23814 | 1 | 5 | 0 | 2 | 0 | 0 |
430 | 5390 | 1 | 0 | 1 | 2 | 1 | 0 |
519 | 96 | 5 | 1 | 0 | 0 | 0 | 0 |
600 | 980 | 2 | 0 | 1 | 2 | 0 | 0 |
670 | 125 | 0 | 0 | 3 | 0 | 0 | 0 |
817 | 39204 | 2 | 4 | 0 | 0 | 2 | 0 |
860 | 21560 | 3 | 0 | 1 | 2 | 1 | 0 |
|
Решая линейную систему уравнений получаем, что
ε⃗ (337)⊕ε⃗ (519)=0⃗ .
Тогда
x=337⋅519mod89755=85148
y=23⋅33⋅71mod89755=1512
85148≢±1512(mod89755)
Следовательно,
u=(86660,89755)=3095
v=(83636,89755)=29.
Получилось разложение 89755=3095⋅29
Вычислительная сложность
Обозначим через Ψ(n,M) количество целых чисел a таких, что
1<a⩽n и a является \Beta-гладким числом, где
\Beta={p:p<M}. Из теоремы де Брёйна — Эрдёша
Ψ(n,M)=n⋅u−u, где u=lnnlnM. Значит,
каждое \Beta-гладкое число будет в среднем попадаться с uu попыток.
Для проверки, является ли число \Beta-гладким, необходимо выполнить
h делений. По алгоритму необходимо найти h+1 \Beta-гладкое число.
Значит, вычислительная сложность поиска чисел
T1=O(uu⋅h2).
Вычислительная сложность метода Гаусса из h уравнений
T2=O(h3).
Следовательно, суммарная сложность алгоритма Диксона
T=T1+T2=O(uu⋅h2+h3).
Учитывая, что количество простых чисел меньше M оценивается формулой
h=MlnM, и что u=lnnlnM, после
упрощения получаем
T=O(exp(lnn⋅lnlnnlnM+lnM)).
M выбирается таким образом, чтобы T было минимально. Тогда
подставляя
L(n)=exp(lnn⋅lnlnn−−−−−−−−−√),
получаем
M=L(n)12
T=O(L(n)2).
Дополнительные стратегии
Рассмотрим дополнительные стратегии, ускоряющие работу алгоритма.
Стратегия
LP
Стратегия LP использует большие простые числа для ускорения процедуры
генерации чисел b.
agraphАлгоритм
Пусть найденное в пункте 4 число a не является \Beta-гладким. Тогда
его можно представить
a=s⋅∏p\isin\Betapαp(b), где
s не делится на числа из факторной базы. Очевидно, что s>M. Если
дополнительно выполняется s<M2, то s — простое и мы включаем его
в факторную базу. Это позволяет найти дополнительные \Beta-гладкие
числа, но увеличивает количество необходимых гладких чисел на 1. Для
возврата к первоначальной факторной базе после пункта 5 следует сделать
следующее. Если найдено только одно число, в разложение которого s
входит в нечетной степени, то это число нужно вычеркнуть из списка и
вычеркнуть s из факторной базы. Если же, например, таких чисел два
b1 и b2, то их нужно вычеркнуть и добавить число
b=b1⋅b2. Показатель 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, и если после разложения
неразложенная часть остается больше, чем n1−m, то данное b
отбрасывается.
agraphВариация
стратегии
Можно использовать стратегию EAS с несколькими обрывами, то есть при
некоторой возрастающей последовательности lj и и убывающей
последовательности mj.
agraphВычислительная
сложность
Алгоритм Диксона с применением стратегии EAS при
k=27√,l=12,m=17 оценивается
TEAS=O(L(n)72√).
Стратегия
PS
Стратегия PS использует алгоритм Полларда-Штрассена, который для
z,t∈N и y=z2 находит минимальный простой делитель
числа НОД(t,y!) за O(z⋅ln2z⋅ln2t).
agraphАлгоритм
Выбирается фиксированное 0<k<1. В алгоритме Диксона a
факторизуется пробными делениями на
p<M=L(n)12. В стратегии PS выбирается
M=L(n)k. Полагаем
z=[L(n)k2]+1,y=z2⩾L(n)k,t=a.
Применяем алгоритм Полларда-Штрассена, выбирая за t неразложенную
часть, получим разложение a.
agraphВычислительная
сложность
Сложность алгоритма Диксона со стратегией PS минимальна при
k=13√ и равна
TPS=O(L(n)3√).