- Теория чисел
- Общие разделы
- Теоретико числовые алгоритмы
- Алгоритмы факторизации
- ........................
- ........................
Алгоритм Диксона
Алгоритм Диксона — алгоритм факторизации, использующий в
своей основе идею Лежандра, заключающуюся в поиске пары целых чисел xx
и yy таких, что x2≡y2(modn)x2≡y2(modn) и
x≢±y(modn).x≢±y(modn).
Метод Диксона является обобщением метода Ферма.
В 20-х г. XX столетия Морис Крайчик (1882—1957), обобщая теорему Ферма предложил вместо пар чисел, удовлетворяющих уравнению x2−y2=nx2−y2=n ,
искать пары чисел, удовлетворяющих более общему уравнению
x2≡y2(modn)x2≡y2(modn) . Крайчик заметил несколько полезных для решения
фактов. В 1981 г. Джон Диксон опубликовал разработанный им метод
факторизации, использующий идеи Крайтчика, и рассчитал его
вычислительную сложность.
Составить факторную базу \Beta={p1,p2,…,ph}\Beta={p1,p2,…,ph} ,
состоящую из всех простых чисел
p<=M=L(n)12p<=M=L(n)12 , где
L(n)=exp(√lnn⋅lnlnn)L(n)=exp(lnn⋅lnlnn−−−−−−−−−√) .
Выбрать случайное $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,1⩽t⩽mε⃗ (bi1)⊕⋯⊕ε⃗ (bit)=0⃗ ,1⩽t⩽m
и положить:
x=bi1…bitmodnx=bi1…bitmodn
y=∏p\isin\Betap(αp(bi1)+⋯+αp(bit))2modny=∏p\isin\Betap(αp(bi1)+⋯+αp(bit))2modn .
Проверить x≡±y(modn)x≡±y(modn) . Если это так, то повторить
процедуру генерации. Если нет, то найдено нетривиальное разложение:
n=u⋅v,u=(x+y,n),v=(x−y,n).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(αp(bi1)+⋯+αp(bit))mod2=(εp(bi1)+⋯+εp(bit))mod2=ε(bi1)⊕⋯⊕ε(bit)=0
x2≡y2(modn)x2≡y2(modn) следует из того, что:
x2=b2i1…b2it≡∏p\isin\Betapαp(bi1)+⋯+αp(bit)(modn)x2=b2i1…b2it≡∏p\isin\Betapαp(bi1)+⋯+αp(bit)(modn)
y2=∏p\isin\Betapαp(bi1)+⋯+αp(bit)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) записываем в таблицу.
Решая линейную систему уравнений получаем, что →ε(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 использует большие простые числа для ускорения процедуры генерации чисел 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 (раннего обрыва) исключает некоторые 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 использует алгоритм Полларда-Штрассена, который для 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=1√3 и равна
TPS=O(L(n)√3).
Метод Диксона является обобщением метода Ферма.
История
В 20-х г. XX столетия Морис Крайчик (1882—1957), обобщая теорему Ферма предложил вместо пар чисел, удовлетворяющих уравнению x2−y2=n
Описание алгоритма
Составить факторную базу \Beta={p1,p2,…,ph}
Выбрать случайное $b, \sqrt{n}
Проверить число a
→α(b)=(αp1(b),…,αph(b))
→ε(b)=(αp1(b)mod2,…,αph(b)mod2)
Повторять процедуру генерации чисел b
Методом Гаусса найти линейную зависимость среди векторов →ε(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=1√3 и равна
TPS=O(L(n)√3).