Эта статья входит в число добротных статей

Факторизация методом непрерывных дробей

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В теории чисел факторизация методом непрерывных дробей (CFRAC) — это алгоритм разложения целых чисел на простые множители. Это алгоритм общего вида, пригодный для факторизации произвольного целого m.

Метод непрерывных дробей разработан на основе алгоритма Крайчика и использует непрерывную дробь, сходящуюся к \sqrt{km} для некоторого целого положительного числа k. На основе метода непрерывных дробей был построен алгоритм Диксона, по схеме которого затем был разработан метод квадратичного решета[1].

Алгоритм имеет сложность O\left(e^{\sqrt{2\log m \log\log m}}\right)=L_m\left[1/2,\sqrt{2}\right], в O и L нотациях.[2]

История[править | править вики-текст]

Метод непрерывных дробей был предложен Д. Г. Лемеромruen и Р. Е. Поверсомruen в 1931 году[3]. Этот метод основывался на идеях Лежандра и Крайчикаruen и предназначался для разложения больших чисел, содержащих 30 и более десятичных разрядов. Однако, полученный метод не применялся из-за трудностей, связанных с его реализацией на настольных арифмометрах[4].

В конце 1960-х годов Джон Бриллхартruen обнаружил, что этот метод хорошо подходит для компьютерного программирования, и совместно с Михаэлем А. Моррисоном переработал этот алгоритм для ЭВМ в 1975 году[5].

В 1970-е годы алгоритм факторизации методом непрерывных дробей стал лучшим средством разложения на простые множители с использованием формата многократной точности. Программа, написанная Моррисоном и Бриллхартом, на компьютере IBM 360/91 обрабатывала произвольные 25-значные числа за 30 секунд, а 40-значные числа — за 50 минут. В 1970 году с помощью именно этого алгоритма была произведена факторизация седьмого числа Ферма[4]:

2^{2^{7}}+1 = 59 649 589 127 497 217 \cdot  5 704 689 200 685 129 054 721.

Метод оставался популярным вплоть до начала 1980-х годов, когда появился метод квадратичного решета. После этого метод факторизации непрерывных дробей оказался неконкурентноспособным.[6]

Описание алгоритма[править | править вики-текст]

Метод Лемера и Пауэрса[править | править вики-текст]

В 1643 году Пьер Ферма предложил алгоритм разложения на множители нечетного целого числа m. Кратко этот алгоритм можно описать так: пусть m = ab. Тогда, можно записать

ab = \left ( \frac{a+b}{2} \right ) ^ 2 - \left ( \frac{a-b}{2} \right ) ^ 2 = x^2 - y^2 = m ,

где x = \frac {a+b}{2}, y = \frac{a-b}{2}.

Отсюда видно, что x^2 - m = y^2. Значит, если последовательно перебирать квадраты целых чисел x, начиная с ближайшего сверху к m квадрата, то на некоторой итерации разность x^2 - m окажется равна квадрату некоторого числа y. Найденная пара чисел (x,y) позволит найти пару множителей (a,b) числа m: a = \frac {x+y}{2}, b = \frac{x-y}{2}.

Таким образом, метод Ферма сводит задачу факторизации числа к поиску целых чисел, разность которых равна исходному числу m. Метод Ферма быстро находит множители числа m в том случае, когда его делители близки к \sqrt{m}, т.е. для максимально негладких чисел. Если же число m является гладким, то метод Ферма может работать даже медленней метода пробных делений[2].

В 1926 году Морис Крайчикruen в монографии[7] представил свой метод факторизации целых чисел, который представлял собой "усиление" метода Ферма.

Крайчик предложил вместо пар чисел (x,y), удовлетворяющих соотношению x^2 - y^2 = m , искать пары (x,y), удовлетворяющие сравнению x^2 - y^2 \equiv 0 \pmod m , т.е. x^2 \equiv y^2 \pmod m . Если, при этом, x \equiv \pm y \pmod m , то мы получим лишь тривиальное решение. Однако, если x \not \equiv \pm y \pmod m , то из указанного сравнения получается x^2 - y^2 = (x - y)(x + y) = k m , где  k \in \mathbb{Z} . Отсюда тоже следует разложение: m делится на (x-y)(x+y), но не делится ни на x-y, ни на x+y, следовательно \gcd(x-y, m) - нетривиальный делитель m[2]. (см. #обоснование1)

После нововведения Крайчика алгоритм нахождения делителей числа m значительно изменялся: теперь по-прежнему нужно вычислять x^2 - m для разных x, однако теперь не требуется "ждать" другой квадрат, а нужно пытаться его построить, перемножая полученные числа m[2].

Действительно, рассмотрим последовательность чисел вида \upsilon (u) = u^2 - m (очевидно, \upsilon \equiv u^2 \pmod m). Тогда, если  \upsilon (u_1) \upsilon (u_2) \dots \upsilon (u_k) = y^2 , т.е. (u_1^2 - m)(u_2^2 - m) \dots (u_k^2 - m) = y^2 , то отсюда следует, что x^2 = u_1^2 u_2^2 \dots u_k^2 \equiv y^2 \pmod m[2]. Для того, чтобы определить, какие именно соотношения нужно перемножить, необходимо раскладывать числа \upsilon на множители и перемножать соотношения так, чтобы в произведениях \upsilon_1 \upsilon_2 \dots \upsilon_k присутствовали простые множители в четных степенях, позволяющие получить сравнение x^2 \equiv y^2 \pmod m[8].

Метод Крайчика сводит задачу разложения числа m на множители к построению некоторого количества сравнений u^2 \equiv \upsilon \pmod m и разложению на множители чисел \upsilon. Однако Крайчик не предъявил конкретный алгоритм поиска пар чисел u, \upsilon и алгоритмический способ составления из найденных соотношений сравнения вида x^2 \equiv y^2 \pmod m[8].

В 1931 году в работе[3] Лемер и Пауэрс предложили два варианта генерации указанных сравнений. Оба варианта основывались на соотношениях, возникающих при разложении квадратичных иррациональностей в непрерывные дроби, и обладали тем свойством, что величины \upsilon не превосходили 2 \sqrt{m}[9]. Последнее неравенство гарантирует, что числа \upsilon будут маленькими, что облегчит разложение этих чисел на простые множители[2].(см. #обоснование2)

При этом, оба варианта оказываются эквивалентными[3]: если один вариант алгоритма найдет решение, то и второй вариант также найдет решение.

Однако, у обоих вариантов алгоритма был недостаток — разложение квадратичной иррациональности в непрерывную дробь периодично (теорема Лагранжа). Поэтому количество соотношений, которые можно получить с помощью данного метода, ограниченно, и их может оказаться недостаточно для набора соотношений и построения сравнения x^2 \equiv y^2 \pmod m. При этом, как показывают практические эксперименты, при больших значениях m длина периода разложения в непрерывную дробь оказывается достаточно большой(порядка \sqrt{m}[10]) для составления требуемого числа сравнений. В результате при больших m оба варианта алгоритма всегда находят разложение числа m на множители[11].

Первый вариант[править | править вики-текст]

Напомним, что каждому действительному числу \xi может быть поставлена в соответствие последовательность целых чисел [b_0 , b_1 , b_2 , . . . ], называемая его непрерывной дробью. Это сопоставление строится следующим образом

x_0 = \xi,\quad b_i = [x_i],\quad x_{i+1} = \frac{1}{x_i - b_i},\quad i = 0,1,2,\dots .

При этом \xi = b_0 + \frac{1}{b_1 + \frac{1}{b_2 + \frac{1}{\dots + \frac{1}{x_n}}}} = [b_0 , b_1 , b_2 , \dots , b_{n-1}, x_n ].

Если раскладывать в непрерывную дробь число \xi = \sqrt{m}, то возникающие в процессе разложения числа x_n имеют вид x_n = \frac{\sqrt{m} + A_n}{B_n} с целыми A_n, B_n, причем выполняется  A_n < \sqrt{m}, 0 < B_n < 2 \sqrt{m}[12].

Для коэффициентов A_n, B_n выполняется равенство[3]:

A_n^2 + B_n B_{n-1} = m.

Отсюда следует

-B_n B_{n-1} \equiv A_n^2 \pmod m,\quad n = 0,1, \dots ~(1).

Полученное равенство имеет вид u^2 \equiv \upsilon \pmod m, предложенный Крайчиком, и может быть применено для факторизации числа m.

Вычисляя последовательно частные A_0,B_0, A_1, B_1, \dots, будем получать выражения вида (1) для различных n. Раскладывая величины B_n на простые множители и комбинируя полученные равенства, можно получить сравнения вида x^2 \equiv y^2 \pmod m (см. #пример1).

Второй вариант[править | править вики-текст]

С каждой непрерывной дробью свяжем последовательность рациональных чисел, состоящую из подходящих дробей \frac{P_n}{Q_n} = [b_0, b_1, \dots , b_{n-1}, b_n], n > 0, вычисляемых по формулам[3]:

P_{n+1} = b_{n+1} P_n + P_{n-1},\quad Q_{n+1} = b_{n+1} Q_n + Q_{n-1},\quad n \geqslant 0,
P_0 = b_0,\quad Q_0 = P_{-1} = 1, \quad Q_{-1} = 0

и стремящихся к разлагаемому числу. Если в непрерывную дробь разлагается число \xi =\sqrt{m}, то справедливо соотношение[12]:

P^2_{n-1} - m Q_{n-1}= (-1)^n B_n ,

из которого следует

P^2_{n-1} \equiv (-1)^n B_n \pmod m, n = 1,2, \dots ~(2).

Полученное равенство имеет вид u^2 \equiv \upsilon \pmod m, и может быть использовано для факторизации числа m так же, как и в первом варианте.

Алгоритм[править | править вики-текст]

Таким образом, исправленный Лемером и Пауэрсом метод Крайчика имеет следующий вид[13].

Вход. Составное число m.

Выход. Нетривиальный делитель p числа m.

  1. Разложить \sqrt{m} в непрерывную дробь.
  2. Используя равенства (1) или (2), получить множество сравнений вида u^2 \equiv \upsilon \pmod m и разложить числа \upsilon на простые множители.
  3. Выбрать те равенства u^2 \equiv \upsilon \pmod m, перемножение которых даст произведение четных степеней простых чисел, полученных в резельтате разложения чисел \upsilon. Тем самым, мы получим соотношение вида x^2 \equiv y^2 \pmod m.
  4. Если x \equiv \pm y \pmod m, то вернуться на шаг 3. Если имеющегося числа соотношений недостаточно для генерации равенства x^2 \equiv y^2 \pmod m, то необходимо продолжить разложение числа \sqrt{m} в непрерывную дробь и , затем, вернуться на шаг 2.
  5. С помощью алгоритма Евклида определить p = \gcd (x - y,m).

Лемер и Пауэрс в своей работе указали, как можно генерировать соотношения вида u^2 \equiv \upsilon \pmod m, однако они, также как и Крайчик, не дали алгоритмического способа составления из найденных соотношений сравнения x^2 \equiv y^2 \pmod m. Эту проблему решил метод Моррисона и Бриллхарта.

Метод Моррисона и Бриллхарта[править | править вики-текст]

В начале 1970-х годов в статье[5] Майкл Моррисон и Джон Бриллхарт предложили свой алгоритм, являющийся модификацией второго варианта алгоритма Лемера и Пауэрса. В настоящее время под методом непрерывных дробей понимают именно алгоритм Моррисона и Бриллхарта.

Основное отличие реализованного Моррисоном и Бриллхартом алгоритма от первоначального варианта заключалось в введении процедуры алгоритмического построения сравнения x^2 \equiv y^2 \pmod m по заданному множеству сравнений вида u^2 \equiv \upsilon \pmod m. Для реализации этой процедуры использовалось понятие «факторной базы»[11].

Будем искать x как произведение таких чисел u_i, что наименьший по абсолютной величине вычет числа u_i^2 по модулю m является произведением простых чисел[14]. Тогда из тех же простых чисел можно построить и y.

Базой факторизации (или факторной базой) натурального числа m называется множество B = \{ p_0, p_1, \dots, p_h \} различных простых чисел p_i, за возможным исключением p_0, которое может быть равным -1. При этом число b, для которого b^2\bmod m является произведением степеней чисел из множества B, называется B-гладким числом. Пусть теперь u_i — B-гладкие числа, \upsilon_i = u_i^2\bmod m = \prod_{j=0}^h p_j^{\alpha_{ij}} — разложения их наименьшие по абсолютной величине вычетов по модулю m. Положим

\mathbf{e}_i = (e_{i0}, e_{i1}, \dots, e_{ih}) \in \mathbb{F}^h_2,

где e_{ij} \equiv \alpha_{ij} \mod 2, \mathbb{F}^h_2векторное пространство над полем GF(2), которое состоит из наборов нулей и единиц размерности h.

Подберем числа u_i так, чтобы сумма векторов \mathbf{e}_i была равна нулю. Определим

x = \left(\prod_i u_i\right) \bmod m, \quad y = \prod_{j=0}^h p_j^{\gamma_j},

где \gamma_j = \frac{1}{2} \sum_i \alpha_{ij}. Тогда x^2 \equiv y^2 \pmod m.

Осталось добавить, что факторная база в алгоритме Моррисона и Бриллхарта состоит из тех простых чисел p_i, по модулю которых m является квадратичным вычетом[15].

Алгоритм[править | править вики-текст]

Алгоритм Моррисона и Бриллхарта выглядит следующим образом[16].

Вход. Составное число m.

Выход. Нетривиальный делитель p числа m.

1. Построить базу разложения B = \{p_0, p_1, \dots, p_h\}, где p_0=-1 и p_1, \dots, p_h — попарно различные простые числа, по модулю которых m является квадратичным вычетом.

2. Берутся целые числа u_i, являющиеся числителями подходящих дробей к обыкновенной непрерывной дроби, выражающей число \sqrt{m}. Из этих числителей выбираются h+2 чисел, для которых абсолютно наименьшие вычеты u_i^2 по модулю m являются B-гладкими:

u_i^2 \bmod m = \prod^h_{j=0}p_j^{\alpha_{ij}} = \upsilon_i,

где \alpha_{ij} \geqslant 0. Также каждому числу u_i сопоставляется вектор показателей (\alpha_{i0}, \alpha_{i1}, \dots, \alpha_{ih}).

3. Найти (например, методом Гаусса) такое непустое множество K \subseteqq \{1, 2, \dots, h+1\}, что \oplus_{i \in K}\mathbf{e}_i = 0, где \oplus — операция исключающее ИЛИ, \mathbf{e}_i = (e_{i1}, e_{i2}, \dots, e_{ih} ), e_{ij} \equiv \alpha_{ij} \pmod 2, 0 \leqslant j \leqslant h.

4. Положить x \leftarrow \prod_{i \in K} u_i \bmod m,\quad y \leftarrow \prod_{j = 1}^{h} p_j^{\frac{1}{2} \sum_{i \in K} \alpha_{ij} } \bmod m . Тогда x^2 \equiv y^2 \pmod m.

5. Если x \not\equiv y \pmod m, то положить p \leftarrow \gcd(x - y, m) и выдать результат: p.

В противном случае вернуться на шаг 3 и поменять множество K. (Обычно есть несколько вариантов выбора множества K для одной и той же факторной базы B. Если все возможности исчерпаны, то следует увеличить размер факторной базы).

Из полученного алгоритма впоследствии был разработан алгоритм Диксона, из которого был удален аппарат цепных дробей[17]. После создания алгоритма Диксона, метод непрерывных дробей, по сути, представлял собой алгоритм Диксона, в котором был уточнен выбор абсолютно наименьшего вычета u_i[18].

Некоторые улучшения[править | править вики-текст]

Пусть m = p\cdot q. Выше в непрерывную дробь раскладывалось число \sqrt{m}. Такой вариант эффективен, когда p и q близки друг к другу. Однако, чем больше разность между числами p и q, тем более трудоемким становится алгоритм. В этом случае вместо \sqrt{m} можно раскладывать в непрерывную дробь число \sqrt{km} , где маленький множитель k подбирается так, чтобы в базу множителей вошли все малые простые[19].

Кроме того, так как метод непрерывных дробей построен по схеме алгоритма Диксона, то для него применимы дополнительные стратегии алгоритма Диксона.

Обоснование[править | править вики-текст]

Следующая лемма показывает, что если выполнено сравнение x^2 \equiv y^2 \pmod m и x \not \equiv y \pmod m, то числа x - y и m имеют общие делители.

Лемма(о факторизации)[20]. Пусть m — нечётное составное число и x,y — вычеты по модулю m такие, что x \not \equiv \pm y \pmod m и x^2 \equiv y^2 \pmod m. Тогда выполняется неравенство 1 < \gcd (x - y, m) < m.

Следующие два утверждения — ключевые для алгоритма факторизации методом непрерывных дробей. Они показывают, что можно найти последовательность чисел u_i, квадраты которых имеют малые вычеты по модулю m.

Теорема[21]. Если \frac{P_n}{Q_n}, где n = 1, 2, \dots, — подходящие дроби к числу \alpha > 1, которое задано обыкновенной непрерывной дробью, то для всех n справедлива оценка |P_n^2 - \alpha ^2 Q_n^2| < 2 \alpha .

Следствие[21]. Пусть положительное число m не является полным квадратом и \frac{P_n}{Q_n}, где n = 1, 2, \dots, — подходящие дроби к числу \sqrt{m}. Тогда для абсолютно наименьшего вычета P^2_n \bmod m (т.е. для вычета, расположенного между -\frac{m}{2} и \frac{m}{2}) справедливо неравенство |P_n^2 \bmod m | < 2 \sqrt{m}, причем P_n^2 \bmod m = P_n^2 - m Q^2_n.

Примеры[править | править вики-текст]

Пример 1[22]

Разложим на множители первым алгоримом Лемера и Пауэрса число m = 1081.

1. Будем раскладывать число \xi = \sqrt{m} = \sqrt{1081} в непрерывную дробь и записывать числа A_n, B_n в таблицу для получения уравнений вида u^2 \equiv \upsilon \pmod m.

Таблица: факторизация числа 1081
i xi Ai Bi
1 \frac{32 + \sqrt{1081}}{57} 32 57
2 \frac{25 + \sqrt{1081}}{8} 25 8
3 \frac{31 + \sqrt{1081}}{15} 31 15
4 \frac{29 + \sqrt{1081}}{16} 29 16
5 \frac{19 + \sqrt{1081}}{45} 19 45
6 \frac{26 + \sqrt{1081}}{9} 26 9

2. Теперь запишем сравнения -B_n B_{n-1} \equiv A^2_n \pmod m для n = 2, 3, 4, 5, 6.

-2^3 \cdot 3 \cdot 19 \equiv 25^2 \pmod{1081}
-2^3 \cdot 3 \cdot 5 \equiv 31^2 \pmod{1081}
-2^4 \cdot 3 \cdot 5 \equiv 29^2 \pmod{1081}
-2^4 \cdot 3^2 \cdot 5 \equiv 19^2 \pmod{1081}
-3^4 \cdot 5 \equiv 26^2 \pmod{1081}

3. Перемножая четвертое и пятое сравнения, получим

(-1)^2 \cdot 2^4 \cdot 3^2 \cdot 5 \cdot 3^4 \cdot 5 \equiv 19^2 \cdot 26^2 \pmod{1081}

Приводя подобные множители и сокращая на 3^2,

2^4 \cdot 3^6 \cdot 5^2 \equiv 19^2 \cdot 26^2 \pmod{1081} или 540^2 \equiv 494^2 \pmod{1081}

4. Получили сравнение вида x^2 \equiv y^2 \pmod m, используя которое можно найти делитель числа 1081. Действительно, \gcd (540 - 494, 1081) = 23. Тогда, второй делитель числа 1081 равен 47.

Пример 2[23]

Разложим на множители методом Морриса и Брилхарта число m = 21299881.

1. Строим базу разложения из маленьких простых чисел, выбирая числа, по модулю которых m является квадратичным вычетом, что проверяется вычислением символов Лежандра:

\left ( \frac{m}{3} \right ) = \left ( \frac{m}{5} \right ) = \left ( \frac{m}{7} \right ) = \left ( \frac{m}{11} \right ) = \left ( \frac{m}{19} \right ) = 1.

Отсюда, факторная база будет равна B = \{-1, 2, 3, 5, 7, 11, 19\}, h = 6.

2. Ищем числители P_i подходящих дробей к числу \sqrt{m}

\sqrt{m} = [4615; {5, 1, 1, 2, 1, 7, 1, 27, 1, 6, 1, 2, 12, 23, 1, 8, 2, 3, 6, 1, 1, 1, \dots }].

Выбираем те из них, для которых значения P_i^2 \bmod m являются B-гладкими. Результаты вычислений записываем в таблицу:

k i Pi P2i \pmod m ei
1 2 27691 -4235 = -1 \cdot 5 \cdot 7 \cdot 11^2 (1, 0, 0, 1, 1, 0, 0)
2 3 50767 2688 = 2^7 \cdot 3 \cdot 7 (0, 1, 1, 0, 1, 0, 0)
3 6 1389169 -7920 = -1 \cdot 2^4 \cdot 3^2 \cdot 5 \cdot 11 (1, 0, 0, 1, 0, 1, 0)
4 13 12814433311 385 = 5 \cdot 7 \cdot 11 (0, 0, 0, 1, 1, 1, 0)
5 16 2764443209657 -3800 = -1 \cdot 2^3 \cdot 5^2 \cdot 19 (1, 1, 0, 0, 0, 0, 1)
6 18 20276855015255 -1331 = -1 \cdot 11^3 (1, 0, 0, 0, 0, 1, 0)
7 19 127498600693396 5415 = 3 \cdot 5 \cdot 19^2 (0, 0, 1, 1, 0, 0, 0)
8 24 2390521616955537 -112 = -1 \cdot 2^4 \cdot 7 (1, 0, 0, 0, 1, 0, 0)

3. Поскольку e_1 \oplus e_3 \oplus e_6 \oplus e_8 = 0 , то получаем

4. x = P_2 \cdot P_6 \cdot P_{18} \cdot P_{24} \equiv 12487442 \pmod m ,

y = 2^4 \cdot 3^1 \cdot 5^1 \cdot 7^1 \cdot 11^3 \cdot 19^0 = 2236080 ,
x^2 \equiv y^2 \equiv 13201055 \pmod m.

5. Условие x \not \equiv \pm y \pmod m выполнено, поэтому вычисляем p = \gcd (x - y, m) = \gcd (10251362, 21299881 ) = 3851 .

Поэтому, 21299881 = 3851 \cdot 5531.

Вычислительная сложность[править | править вики-текст]

С появлением криптосистемы RSA в конце 1970-х годов стала особенно важна вычислительная сложность алгоритмов факторизации[2].

Эвристический анализ времени выполнения алгоритма Морриса и Брилхарта был проведен Р. Шруппелемruen в 1975 году, хотя не был опубликован[24][2].

Более точная оценка(которая при этом все равно оставалась эвристической) была проведена в работе[25]. Приведем результаты оценки сложности в соответствии с этой работой.

При получении оценок в этой работе делаются некоторые эвристические допущения. Например, предполагают, что если помощью алгоритма построено 1 + [\log^2 m] пар (x, y) таких, что x^2 \equiv y^2 \pmod m, то хотя бы для одной из них выполнены неравенства

1 < \gcd (x \pm y, m) .

Утверждение[26]. Если a = \frac{1}{\sqrt{2}}, L = L(m) = \exp((\log m \log \log m)^{1/2} ) и факторная база состоит из p = -1 и всех простых чисел p таких, что

 2 \leqslant p \leqslant L^a, \quad \left ( \frac{m}{p} \right ) = +1,

то при вычислении L^b подходящих дробей (где b = a + \frac{1}{4a}) можно ожидать, что алгоритм разложит m на два множителя с эвристической оценкой сложности L_m[ \frac{1}{2}; 2] арифметических операций.

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Кнут, 2007, pp. 439,441.
  2. 1 2 3 4 5 6 7 8 Pomerance, 1996.
  3. 1 2 3 4 5 Lehmer, Powers, 1931.
  4. 1 2 Кнут, 2007, pp. 434.
  5. 1 2 Morrison, Brillhart, 1975.
  6. Маховенко, 2006, pp. 223.
  7. Kraitchik M. Théorie des Nombres. Tome I et II. — Paris:Gauthier-Villars. — 1926.
  8. 1 2 Нестеренко, 2012, pp. 173.
  9. Нестеренко, 2012, pp. 175.
  10. Ященко, 2012, pp. 113.
  11. 1 2 Нестеренко, 2012, pp. 178.
  12. 1 2 Ященко, 1999, pp. 112-113.
  13. Нестеренко, 2012, pp. 173,185.
  14. Манин, 1990, pp. 78.
  15. Маховенко, 2006, pp. 220.
  16. Маховенко, 2006, pp. 218-220.
  17. Кнут, 2007, pp. 439.
  18. Маховенко, 2006, pp. 219.
  19. Ященко, 2006, pp. 114.
  20. Нестеренко, 2012, pp. 172.
  21. 1 2 Маховенко, 2006, pp. 219-220.
  22. Нестеренко, 2012, pp. 176-177.
  23. Маховенко, 2006, pp. 221-222.
  24. Кнут, 2001, pp. 436.
  25. Pomerance, 1982.
  26. Василенко, 2003, pp. 87.

Литература[править | править вики-текст]