Алгоритм Диксона
Алгоритм Диксона — алгоритм факторизации, использующий в своей основе идею Лежандра, заключающуюся в поиске пары целых чисел <math>x</math> и <math>y</math> таких, что <math>x^2 \equiv y^2\pmod{n}</math> и <math>x \not\equiv \pm y\pmod{n}.</math>
Метод Диксона является обобщением метода Ферма.
Содержание
История [1]
В 20-х г. XX столетия Морис Крайчик (1882-1957), обобщая теорему Ферма предложил вместо пар чисел, удовлетворяющих уравнению <math>x^2 - y^2 = n</math>, искать пары чисел, удовлетворяющих более общему уравнению <math>x^2 \equiv y^2\pmod{n}</math>. Крайчик заметил несколько полезных для решения фактов. В 1981 г. Джон Диксон опубликовал разработанный им метод факторизации, использующий идеи Крайтчика, и рассчитал его вычислительную сложность.[2]
Описание алгоритма [3]
- Составить факторную базу <math>\Beta = \left\{ {p_1,p_2,\dots,p_h} \right\}</math>, состоящую из всех простых чисел <math>p <= M = L\left({n}\right)^{\frac{1}{2}}</math>, где <math>L\left({n}\right)=\exp{\left({\sqrt{\ln{n}\cdot \ln{\ln{n}}}}\right)}</math>.
- Выбрать случайное <math>b, \sqrt{n}<b<n</math>
- Вычислить <math>a = b^2\bmod{n}</math>.
- Проверить число <math>a</math> на гладкость пробными делениями. Если <math>a</math> является <math>\Beta</math>-гладким числом, то есть <math>a = \prod_{p\isin \Beta}p^{\alpha_{p}\left({b}\right)}</math>, следует запомнить вектора <math>\vec{\alpha}\left({b}\right)</math> и <math>\vec{\varepsilon}\left({b}\right)</math>:
- <math>\vec{\alpha}\left({b}\right)=\left({\alpha_{p_1}\left({b}\right), \dots, \alpha_{p_h}\left({b}\right)}\right)</math>
- <math>\vec{\varepsilon}\left({b}\right)=\left({\alpha_{p_1}\left({b}\right)\bmod{2}, \dots, \alpha_{p_h}\left({b}\right)\bmod{2}}\right)</math>.
- Повторять процедуру генерации чисел <math>b</math> до тех пор, пока не будет найдено <math>h+1</math> <math>\Beta</math>-гладких чисел <math>b_1,...,b_{h+1}</math>.
- Методом Гаусса найти линейную зависимость среди векторов <math>\vec{\varepsilon}\left({b_1}\right), \dots, \vec{\varepsilon}\left({b_{h+1}}\right)</math>:
- <math>\vec{\varepsilon}\left({b_{i_1}}\right)\oplus\dots\oplus\vec{\varepsilon}\left({b_{i_t}}\right)=\vec{0}, 1 \leqslant t \leqslant m</math>
- <math>x=b_{i_1} \dots b_{i_t}\bmod{n}</math>
- <math>y=\prod_{p\isin\Beta}p^{\left({ \alpha_p\left({b_{i_1}}\right)+\dots+\alpha_p\left({b_{i_t}}\right) }\right) \over{2}}\bmod{n}</math>.
- Проверить <math>x \equiv \pm y \pmod{n}</math>. Если это так, то повторить процедуру генерации. Если нет, то найдено нетривиальное разложение:
- <math>n=u\cdot v, u=\left({x+y,n}\right), v=\left({x-y,n}\right).</math>
- Чтобы формула для <math>y</math> была корректной, сумма <math>\alpha_p\left({b_{i_1 </div>
- <math>(\alpha_p\left({b_{i_1}}\right)+\dots+\alpha_p\left({b_{i_t}}\right))\bmod{2} = (\varepsilon_p\left({b_{i_1}}\right)+\dots+\varepsilon_p\left({b_{i_t}}\right))\bmod{2} = {\varepsilon}\left({b_{i_1}}\right)\oplus\dots\oplus\varepsilon\left({b_{i_t}}\right) = 0</math></li>
- <math>x^2 = b_{i_1}^2 \dots b_{i_t}^2 \equiv \prod_{p\isin\Beta}p^{{ \alpha_p\left({b_{i_1}}\right)+\dots+\alpha_p\left({b_{i_t}}\right) }}\pmod{n}</math>
- <math>y^2 = \prod_{p\isin\Beta}p^{{ \alpha_p\left({b_{i_1}}\right)+\dots+\alpha_p\left({b_{i_t}}\right) }}</math>
Пример
Факторизуем число <math>n = 89755</math>.
- <math>L(89755) = 194,174...</math>
- <math>M = 13,934...</math>
- <math>\Beta = \left\{ 2, 3, 5, 7, 11, 13 \right\}</math>
Все найденные числа <math>b</math> с соответствующими векторами <math>\vec{\alpha}(b)</math> записываем в таблицу.
<math>b</math> | <math>a</math> | <math>\alpha_2\left({b}\right)</math> | <math>\alpha_3\left({b}\right)</math> | <math>\alpha_5\left({b}\right)</math> | <math>\alpha_7\left({b}\right)</math> | <math>\alpha_{11}\left({b}\right)</math> | <math>\alpha_{13}\left({b}\right)</math> |
---|---|---|---|---|---|---|---|
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 |
Решая линейную систему уравнений получаем, что <math>\vec{\varepsilon}\left(337\right)\oplus\vec{\varepsilon}\left(519\right)=\vec{0}</math>. Тогда
- <math>x = 337 \cdot 519 \bmod{89755}= 85148</math>
- <math>y = 2^3 \cdot 3^3 \cdot 7^1 \bmod{89755} = 1512</math>
- <math>85148 \not\equiv \pm 1512 \pmod{89755}</math>
Следовательно,
- <math>u = (86660, 89755) = 3095</math>
- <math>v = (83636, 89755) = 29</math>.
Получилось разложение <math>89755 = 3095 \cdot 29</math>
Вычислительная сложность [5]
Обозначим через <math>\Psi(n, M)</math> количество целых чисел <math>a</math> таких, что <math>1 < a \leqslant n</math> и <math>a</math> является <math>\Beta</math>-гладким числом, где <math>\Beta = \{p : p < M\}</math>. Из теоремы де Брёйна — Эрдёша <math>\Psi(n, M) = n \cdot u^{-u}</math>, где <math>u = \frac{\ln{n}}{\ln{M}}</math>. Значит, каждое <math>\Beta</math>-гладкое число будет в среднем попадаться с <math>u^u</math> попыток. Для проверки, является ли число <math>\Beta</math>-гладким, необходимо выполнить <math>h</math> делений. По алгоритму необходимо найти <math>h+1</math> <math>\Beta</math>-гладкое число. Значит, вычислительная сложность поиска чисел
- <math>T_1 = O\left({u^{u}\cdot h^{2}}\right)</math>.
Вычислительная сложность метода Гаусса из <math>h</math> уравнений
- <math>T_2 = O\left({h^3}\right)</math>.
Следовательно, суммарная сложность алгоритма Диксона
- <math>T = T_1 + T_2 = O\left({u^{u}\cdot h^{2}+h^{3}}\right)</math>.
Учитывая, что количество простых чисел меньше <math>M</math> оценивается формулой <math>h = \frac{M}{\ln{M}}</math>, и что <math>u = \frac{\ln{n}}{\ln{M}}</math>, после упрощения получаем
- <math>T = O\left( exp(\frac{\ln{n} \cdot \ln{\ln{n}}}{\ln{M}} + \ln{M})\right)</math>.
<math>M</math> выбирается таким образом, чтобы <math>T</math> было минимально. Тогда подставляя <math>L\left({n}\right)=\exp{\left({\sqrt{\ln{n}\cdot \ln{\ln{n}}}}\right)}</math>, получаем
- <math>M=L\left({n}\right)^{\frac{1}{2}}</math>
- <math>T = O\left({L\left({n}\right)}^{2}\right)</math>.
Дополнительные стратегии [6]
Рассмотрим дополнительные стратегии, ускоряющие работу алгоритма.
Стратегия LP
Стратегия LP использует большие простые числа для ускорения процедуры генерации чисел <math>b</math>.
Алгоритм
Пусть найденное в пункте 4 число <math>a</math> не является <math>\Beta</math>-гладким. Тогда его можно представить <math>a = s \cdot \prod_{p\isin \Beta}p^{\alpha_{p}\left({b}\right)}</math>, где <math>s</math> не делится на числа из факторной базы. Очевидно, что <math>s > M</math>. Если дополнительно выполняется <math>s < M^2</math>, то s - простое и мы включаем его в факторную базу. Это позволяет найти дополнительные <math>\Beta</math>-гладкие числа, но увеличивает количество необходимых гладких чисел на 1. Для возврата к первоначальной факторной базе после пункта 5 следует сделать следующее. Если найдено только одно число, в разложение которого <math>s</math> входит в нечетной степени, то это число нужно вычеркнуть из списка и вычеркнуть <math>s</math> из факторной базы. Если же, например, таких чисел два <math>b_1</math> и <math>b_2</math>, то их нужно вычеркнуть и добавить число <math>b = b_1 \cdot b_2</math>. Показатель <math>s</math> войдет в разложение <math>b^2\bmod{n}</math> в четной степени и будет отсутствовать в системе линейных уравнений.
Вариация стратегии
Можно использовать стратегию LP с несколькими простыми числами, не содержащимися в факторной базе. В этом случае для исключения дополнительных простых чисел используется теория графов.
Вычислительная сложность
Теоретическая оценка сложности алгоритма Диксона с применением LP стратегии остается прежней
- <math>T_{LP} = O\left({L\left({n}\right)}^{2}\right)</math>.
Стратегия EAS
Стратегия EAS (раннего обрыва) исключает некоторые <math>b</math> из рассмотрения, не доводя проверку <math>a</math> на гладкость до конца.
Алгоритм
Выбираются фиксированные <math>0 < k, l, m < 1</math>. В алгоритме Диксона <math>a</math> факторизуется пробными делениями на <math>p < M = L\left({n}\right)^{\frac{1}{2}}</math>. В стратегии EAS выбирается <math>M = L\left({n}\right)^{k}</math> и число сначала факторизуется пробными делениями на <math>p < M^l = L\left({n}\right)^{kl}</math>, и если после разложения неразложенная часть остается больше, чем <math>n^{1-m}</math>, то данное <math>b</math> отбрасывается.
Вариация стратегии
Можно использовать стратегию EAS с несколькими обрывами, то есть при некоторой возрастающей последовательности <math>l_j</math> и и убывающей последовательности <math>m_j</math>.
Вычислительная сложность
Алгоритм Диксона с применением стратегии EAS при <math>k = \sqrt{\frac{2}{7}}, l = \frac{1}{2}, m = \frac{1}{7}</math> оценивается
- <math>T_{EAS} = O\left({L\left({n}\right)}^{\sqrt{\frac{7}{2}}}\right)</math>.
Стратегия PS
Стратегия PS использует алгоритм Полларда-Штрассена, который для <math>z, t \in \mathbb{N}</math> и <math>y = z^2</math> находит минимальный простой делитель числа НОД<math>(t, y!)</math> за <math>O\left(z \cdot \ln^2{z} \cdot \ln^2{t}\right)</math>.[7]
Алгоритм
Выбирается фиксированное <math>0 < k < 1</math>. В алгоритме Диксона <math>a</math> факторизуется пробными делениями на <math>p < M = L\left({n}\right)^{\frac{1}{2}}</math>. В стратегии PS выбирается <math>M = L\left({n}\right)^{k}</math>. Полагаем <math>z = [L\left({n}\right)^{\frac{k}{2}}] + 1, y = z^2 \geqslant L\left({n}\right)^{k}, t = a</math>. Применяем алгоритм Полларда-Штрассена, выбирая за <math>t</math> неразложенную часть, получим разложение <math>a</math>.
Вычислительная сложность
Сложность алгоритма Диксона со стратегией PS минимальна при <math>k = \frac{1}{\sqrt{3}}</math> и равна
- <math>T_{EAS} = O\left({L\left({n}\right)}^{\sqrt{3}}\right)</math>.
Напишите отзыв о статье "Алгоритм Диксона"
Примечания
- ↑ Ишмухаметов, 2011, с. 115.
- ↑ Dixon, J. D. (1981). «Asymptotically fast factorization of integers». Math. Comp. 36 (153): 255–260. DOI:10.1090/S0025-5718-1981-0595059-1.
- ↑ Черемушкин, 2002, с. 77-79.
- ↑ Василенко, 2001, с. 79.
- ↑ Черемушкин, 2002, с. 79-80.
- ↑ Василенко, 2001, с. 81-83.
- ↑ Черемушкин, 2002, с. 74-75.
Литература
- Василенко О. Н. [www.ict.edu.ru/ft/002416/book.pdf Теоретико-числовые алгоритмы в криптографии]. — М.: МЦНМО, 2003. — С. 78-83. — 328 с. — ISBN 5-94057-103-4.
- Черемушкин А. В. [www.ict.edu.ru/ft/002419/cherem.pdf Лекции по арифметическим алгоритмам в криптографии]. — М.: МЦНМО, 2001. — С. 74-80. — 104 с. — ISBN 5-94057-060-7.
- Ишмухаметов Ш. Т. [window.edu.ru/resource/980/73980/files/Monograph_ishm.pdf Методы факторизации натуральных чисел: учебное пособие]. — Казань: Казан. ун., 2011. — С. 115-117. — 190 с.
Статья содержит короткие («гарвардские») ссылки на публикации, не указанные или неправильно описанные в библиографическом разделе. Список неработающих ссылок: Василенко, 2001, Черемушкин, 2002 Пожалуйста, исправьте ссылки согласно инструкции к шаблону {{sfn}} и дополните библиографический раздел корректными описаниями цитируемых публикаций, следуя руководствам ВП:Сноски и ВП:Ссылки на источники.
|
Отрывок, характеризующий Алгоритм Диксона
Получив известие о болезни Наташи, графиня, еще не совсем здоровая и слабая, с Петей и со всем домом приехала в Москву, и все семейство Ростовых перебралось от Марьи Дмитриевны в свой дом и совсем поселилось в Москве.Болезнь Наташи была так серьезна, что, к счастию ее и к счастию родных, мысль о всем том, что было причиной ее болезни, ее поступок и разрыв с женихом перешли на второй план. Она была так больна, что нельзя было думать о том, насколько она была виновата во всем случившемся, тогда как она не ела, не спала, заметно худела, кашляла и была, как давали чувствовать доктора, в опасности. Надо было думать только о том, чтобы помочь ей. Доктора ездили к Наташе и отдельно и консилиумами, говорили много по французски, по немецки и по латыни, осуждали один другого, прописывали самые разнообразные лекарства от всех им известных болезней; но ни одному из них не приходила в голову та простая мысль, что им не может быть известна та болезнь, которой страдала Наташа, как не может быть известна ни одна болезнь, которой одержим живой человек: ибо каждый живой человек имеет свои особенности и всегда имеет особенную и свою новую, сложную, неизвестную медицине болезнь, не болезнь легких, печени, кожи, сердца, нервов и т. д., записанных в медицине, но болезнь, состоящую из одного из бесчисленных соединений в страданиях этих органов. Эта простая мысль не могла приходить докторам (так же, как не может прийти колдуну мысль, что он не может колдовать) потому, что их дело жизни состояло в том, чтобы лечить, потому, что за то они получали деньги, и потому, что на это дело они потратили лучшие годы своей жизни. Но главное – мысль эта не могла прийти докторам потому, что они видели, что они несомненно полезны, и были действительно полезны для всех домашних Ростовых. Они были полезны не потому, что заставляли проглатывать больную большей частью вредные вещества (вред этот был мало чувствителен, потому что вредные вещества давались в малом количестве), но они полезны, необходимы, неизбежны были (причина – почему всегда есть и будут мнимые излечители, ворожеи, гомеопаты и аллопаты) потому, что они удовлетворяли нравственной потребности больной и людей, любящих больную. Они удовлетворяли той вечной человеческой потребности надежды на облегчение, потребности сочувствия и деятельности, которые испытывает человек во время страдания. Они удовлетворяли той вечной, человеческой – заметной в ребенке в самой первобытной форме – потребности потереть то место, которое ушиблено. Ребенок убьется и тотчас же бежит в руки матери, няньки для того, чтобы ему поцеловали и потерли больное место, и ему делается легче, когда больное место потрут или поцелуют. Ребенок не верит, чтобы у сильнейших и мудрейших его не было средств помочь его боли. И надежда на облегчение и выражение сочувствия в то время, как мать трет его шишку, утешают его. Доктора для Наташи были полезны тем, что они целовали и терли бобо, уверяя, что сейчас пройдет, ежели кучер съездит в арбатскую аптеку и возьмет на рубль семь гривен порошков и пилюль в хорошенькой коробочке и ежели порошки эти непременно через два часа, никак не больше и не меньше, будет в отварной воде принимать больная.
Что же бы делали Соня, граф и графиня, как бы они смотрели на слабую, тающую Наташу, ничего не предпринимая, ежели бы не было этих пилюль по часам, питья тепленького, куриной котлетки и всех подробностей жизни, предписанных доктором, соблюдать которые составляло занятие и утешение для окружающих? Чем строже и сложнее были эти правила, тем утешительнее было для окружающих дело. Как бы переносил граф болезнь своей любимой дочери, ежели бы он не знал, что ему стоила тысячи рублей болезнь Наташи и что он не пожалеет еще тысяч, чтобы сделать ей пользу: ежели бы он не знал, что, ежели она не поправится, он не пожалеет еще тысяч и повезет ее за границу и там сделает консилиумы; ежели бы он не имел возможности рассказывать подробности о том, как Метивье и Феллер не поняли, а Фриз понял, и Мудров еще лучше определил болезнь? Что бы делала графиня, ежели бы она не могла иногда ссориться с больной Наташей за то, что она не вполне соблюдает предписаний доктора?
– Эдак никогда не выздоровеешь, – говорила она, за досадой забывая свое горе, – ежели ты не будешь слушаться доктора и не вовремя принимать лекарство! Ведь нельзя шутить этим, когда у тебя может сделаться пневмония, – говорила графиня, и в произношении этого непонятного не для нее одной слова, она уже находила большое утешение. Что бы делала Соня, ежели бы у ней не было радостного сознания того, что она не раздевалась три ночи первое время для того, чтобы быть наготове исполнять в точности все предписания доктора, и что она теперь не спит ночи, для того чтобы не пропустить часы, в которые надо давать маловредные пилюли из золотой коробочки? Даже самой Наташе, которая хотя и говорила, что никакие лекарства не вылечат ее и что все это глупости, – и ей было радостно видеть, что для нее делали так много пожертвований, что ей надо было в известные часы принимать лекарства, и даже ей радостно было то, что она, пренебрегая исполнением предписанного, могла показывать, что она не верит в лечение и не дорожит своей жизнью.
Доктор ездил каждый день, щупал пульс, смотрел язык и, не обращая внимания на ее убитое лицо, шутил с ней. Но зато, когда он выходил в другую комнату, графиня поспешно выходила за ним, и он, принимая серьезный вид и покачивая задумчиво головой, говорил, что, хотя и есть опасность, он надеется на действие этого последнего лекарства, и что надо ждать и посмотреть; что болезнь больше нравственная, но…
Графиня, стараясь скрыть этот поступок от себя и от доктора, всовывала ему в руку золотой и всякий раз с успокоенным сердцем возвращалась к больной.
Признаки болезни Наташи состояли в том, что она мало ела, мало спала, кашляла и никогда не оживлялась. Доктора говорили, что больную нельзя оставлять без медицинской помощи, и поэтому в душном воздухе держали ее в городе. И лето 1812 года Ростовы не уезжали в деревню.
Несмотря на большое количество проглоченных пилюль, капель и порошков из баночек и коробочек, из которых madame Schoss, охотница до этих вещиц, собрала большую коллекцию, несмотря на отсутствие привычной деревенской жизни, молодость брала свое: горе Наташи начало покрываться слоем впечатлений прожитой жизни, оно перестало такой мучительной болью лежать ей на сердце, начинало становиться прошедшим, и Наташа стала физически оправляться.
Наташа была спокойнее, но не веселее. Она не только избегала всех внешних условий радости: балов, катанья, концертов, театра; но она ни разу не смеялась так, чтобы из за смеха ее не слышны были слезы. Она не могла петь. Как только начинала она смеяться или пробовала одна сама с собой петь, слезы душили ее: слезы раскаяния, слезы воспоминаний о том невозвратном, чистом времени; слезы досады, что так, задаром, погубила она свою молодую жизнь, которая могла бы быть так счастлива. Смех и пение особенно казались ей кощунством над ее горем. О кокетстве она и не думала ни раза; ей не приходилось даже воздерживаться. Она говорила и чувствовала, что в это время все мужчины были для нее совершенно то же, что шут Настасья Ивановна. Внутренний страж твердо воспрещал ей всякую радость. Да и не было в ней всех прежних интересов жизни из того девичьего, беззаботного, полного надежд склада жизни. Чаще и болезненнее всего вспоминала она осенние месяцы, охоту, дядюшку и святки, проведенные с Nicolas в Отрадном. Что бы она дала, чтобы возвратить хоть один день из того времени! Но уж это навсегда было кончено. Предчувствие не обманывало ее тогда, что то состояние свободы и открытости для всех радостей никогда уже не возвратится больше. Но жить надо было.
Ей отрадно было думать, что она не лучше, как она прежде думала, а хуже и гораздо хуже всех, всех, кто только есть на свете. Но этого мало было. Она знала это и спрашивала себя: «Что ж дальше?А дальше ничего не было. Не было никакой радости в жизни, а жизнь проходила. Наташа, видимо, старалась только никому не быть в тягость и никому не мешать, но для себя ей ничего не нужно было. Она удалялась от всех домашних, и только с братом Петей ей было легко. С ним она любила бывать больше, чем с другими; и иногда, когда была с ним с глазу на глаз, смеялась. Она почти не выезжала из дому и из приезжавших к ним рада была только одному Пьеру. Нельзя было нежнее, осторожнее и вместе с тем серьезнее обращаться, чем обращался с нею граф Безухов. Наташа Осссознательно чувствовала эту нежность обращения и потому находила большое удовольствие в его обществе. Но она даже не была благодарна ему за его нежность; ничто хорошее со стороны Пьера не казалось ей усилием. Пьеру, казалось, так естественно быть добрым со всеми, что не было никакой заслуги в его доброте. Иногда Наташа замечала смущение и неловкость Пьера в ее присутствии, в особенности, когда он хотел сделать для нее что нибудь приятное или когда он боялся, чтобы что нибудь в разговоре не навело Наташу на тяжелые воспоминания. Она замечала это и приписывала это его общей доброте и застенчивости, которая, по ее понятиям, таковая же, как с нею, должна была быть и со всеми. После тех нечаянных слов о том, что, ежели бы он был свободен, он на коленях бы просил ее руки и любви, сказанных в минуту такого сильного волнения для нее, Пьер никогда не говорил ничего о своих чувствах к Наташе; и для нее было очевидно, что те слова, тогда так утешившие ее, были сказаны, как говорятся всякие бессмысленные слова для утешения плачущего ребенка. Не оттого, что Пьер был женатый человек, но оттого, что Наташа чувствовала между собою и им в высшей степени ту силу нравственных преград – отсутствие которой она чувствовала с Kyрагиным, – ей никогда в голову не приходило, чтобы из ее отношений с Пьером могла выйти не только любовь с ее или, еще менее, с его стороны, но даже и тот род нежной, признающей себя, поэтической дружбы между мужчиной и женщиной, которой она знала несколько примеров.