Факторизация методом непрерывных дробей
В теории чисел факторизация методом непрерывных дробей (CFRAC) — это алгоритм разложения целых чисел на простые множители. Это алгоритм общего вида, пригодный для факторизации произвольного целого [math]\displaystyle{ m }[/math].
Метод непрерывных дробей разработан на основе алгоритма Крайчика и использует непрерывную дробь, сходящуюся к [math]\displaystyle{ \sqrt{km} }[/math] для некоторого целого положительного числа [math]\displaystyle{ k }[/math]. На основе метода непрерывных дробей был построен алгоритм Диксона, по схеме которого, затем, был разработан метод квадратичного решета[1].
Алгоритм имеет сложность [math]\displaystyle{ O\left(e^{\sqrt{2\log m \log\log m}}\right)=L_m\left [\frac{1}{2}, \sqrt{2}\right ] }[/math], в O и L нотациях[2].
История
Метод непрерывных дробей был предложен Д. Г. Лемером и Р. Е. Поверсом в 1931 году[3]. Этот метод основывался на идеях Лежандра и Крайчика и предназначался для разложения больших чисел, содержащих 30 и более десятичных разрядов. Однако, полученный метод не применялся из-за трудностей, связанных с его реализацией на настольных арифмометрах[4].
В конце 1960-х годов Джон Бриллхарт обнаружил, что этот метод хорошо подходит для компьютерного программирования, и совместно с Михаэлем А. Моррисоном, переработал этот алгоритм для ЭВМ в 1975 году[5].
В 1970-е годы алгоритм факторизации методом непрерывных дробей стал лучшим средством разложения на простые множители с использованием формата многократной точности. Программа, написанная Моррисоном и Бриллхартом, на компьютере IBM 360/91 обрабатывала произвольные 25-значные числа за 30 секунд, а 40-значные числа — за 50 минут. В 1970 году с помощью именно этого алгоритма была произведена факторизация седьмого числа Ферма[4]:
- [math]\displaystyle{ 2^{2^{7}}+1 = 59 649 589 127 497 217 \cdot 5 704 689 200 685 129 054 721. }[/math]
Метод оставался популярным вплоть до начала 1980-х годов, когда появился метод квадратичного решета. После этого метод факторизации непрерывных дробей оказался неконкурентоспособным[6].
Описание алгоритма
Метод Лемера и Пауэрса
В 1643 году Пьер Ферма предложил алгоритм разложения на множители нечетного целого числа [math]\displaystyle{ m }[/math]. Кратко этот алгоритм можно описать так: пусть [math]\displaystyle{ m = ab }[/math]. Тогда, можно записать
- [math]\displaystyle{ ab = \left ( \frac{a+b}{2} \right ) ^ 2 - \left ( \frac{a-b}{2} \right ) ^ 2 = x^2 - y^2 = m }[/math],
где [math]\displaystyle{ x = \frac {a+b}{2},\quad y = \frac{a-b}{2} }[/math].
Отсюда видно, что [math]\displaystyle{ x^2 - m = y^2 }[/math]. Значит, если последовательно перебирать квадраты целых чисел [math]\displaystyle{ x }[/math], начиная с ближайшего сверху к [math]\displaystyle{ m }[/math] квадрата, то на некоторой итерации разность [math]\displaystyle{ x^2 - m }[/math] окажется равна квадрату некоторого числа [math]\displaystyle{ y }[/math]. Найденная пара чисел [math]\displaystyle{ (x,y) }[/math] позволит найти пару множителей [math]\displaystyle{ (a,b) }[/math] числа [math]\displaystyle{ m }[/math]: [math]\displaystyle{ a = \frac {x+y}{2},\quad b = \frac{x-y}{2} }[/math].
Таким образом, метод Ферма сводит задачу факторизации числа к поиску целых чисел, разность которых равна исходному числу [math]\displaystyle{ m }[/math]. Метод Ферма быстро находит множители числа [math]\displaystyle{ m }[/math] в том случае, когда его делители близки к [math]\displaystyle{ \sqrt{m} }[/math], т.е. для максимально негладких чисел. Если же число [math]\displaystyle{ m }[/math] является гладким, то метод Ферма может работать даже медленней метода пробных делений[2].
В 1926 году Морис Крайчик в монографии[7] представил свой метод факторизации целых чисел, который представлял собой «усиление» метода Ферма.
Крайчик предложил вместо пар чисел [math]\displaystyle{ (x,y) }[/math], удовлетворяющих соотношению [math]\displaystyle{ x^2 - y^2 = m }[/math], искать пары [math]\displaystyle{ (x,y) }[/math], удовлетворяющие сравнению [math]\displaystyle{ x^2 - y^2 \equiv 0 \pmod m }[/math], т.е. [math]\displaystyle{ x^2 \equiv y^2 \pmod m }[/math]. Если, при этом, [math]\displaystyle{ x \equiv \pm y \pmod m }[/math], то мы получим лишь тривиальное решение. Однако, если [math]\displaystyle{ x \not \equiv \pm y \pmod m }[/math], то из указанного сравнения получается [math]\displaystyle{ x^2 - y^2 = (x - y)(x + y) = k m }[/math], где [math]\displaystyle{ k \in \mathbb{Z} }[/math]. Отсюда тоже следует разложение: [math]\displaystyle{ m }[/math] делится на [math]\displaystyle{ (x-y)(x+y) }[/math], но не делится ни на [math]\displaystyle{ x-y }[/math], ни на [math]\displaystyle{ x+y }[/math], следовательно [math]\displaystyle{ \gcd(x-y, m) }[/math] — нетривиальный делитель [math]\displaystyle{ m }[/math][2] (см. #обоснование1).
После нововведения Крайчика алгоритм нахождения делителей числа [math]\displaystyle{ m }[/math] значительно изменялся: теперь по-прежнему нужно вычислять [math]\displaystyle{ x^2 - m }[/math] для разных [math]\displaystyle{ x }[/math], однако теперь не требуется «ждать» другой квадрат, а нужно пытаться его построить, перемножая полученные числа [math]\displaystyle{ m }[/math][2].
Действительно, рассмотрим последовательность чисел вида [math]\displaystyle{ \upsilon (u) = u^2 - m }[/math] (очевидно, [math]\displaystyle{ \upsilon \equiv u^2 \pmod m }[/math]). Тогда, если [math]\displaystyle{ \upsilon (u_1) \upsilon (u_2) \dots \upsilon (u_k) = y^2 }[/math], т.е. [math]\displaystyle{ (u_1^2 - m)(u_2^2 - m) \dots (u_k^2 - m) = y^2 }[/math], то отсюда следует, что [math]\displaystyle{ x^2 = u_1^2 u_2^2 \dots u_k^2 \equiv y^2 \pmod m }[/math][2]. Для того, чтобы определить, какие именно соотношения нужно перемножить, необходимо раскладывать числа [math]\displaystyle{ \upsilon }[/math] на множители и перемножать соотношения так, чтобы в произведениях [math]\displaystyle{ \upsilon_1 \upsilon_2 \dots \upsilon_k }[/math] присутствовали простые множители в четных степенях, позволяющие получить сравнение [math]\displaystyle{ x^2 \equiv y^2 \pmod m }[/math][8].
Метод Крайчика сводит задачу разложения числа [math]\displaystyle{ m }[/math] на множители к построению некоторого количества сравнений [math]\displaystyle{ u^2 \equiv \upsilon \pmod m }[/math] и разложению на множители чисел [math]\displaystyle{ \upsilon }[/math]. Однако Крайчик не предъявил конкретный алгоритм поиска пар чисел [math]\displaystyle{ u, \upsilon }[/math] и алгоритмический способ составления из найденных соотношений сравнения вида [math]\displaystyle{ x^2 \equiv y^2 \pmod m }[/math][8].
В 1931 году в работе[3] Лемер и Пауэрс предложили два варианта генерации указанных сравнений. Оба варианта основывались на соотношениях, возникающих при разложении квадратичных иррациональностей в непрерывные дроби, и обладали тем свойством, что величины [math]\displaystyle{ \upsilon }[/math] не превосходили [math]\displaystyle{ 2 \sqrt{m} }[/math] [9]. Последнее неравенство гарантирует, что числа [math]\displaystyle{ \upsilon }[/math] будут маленькими, что облегчит разложение этих чисел на простые множители[2](см. #обоснование2).
При этом, оба варианта оказываются эквивалентными[3]: если один вариант алгоритма найдет решение, то и второй вариант также найдет решение.
Однако, у обоих вариантов алгоритма был недостаток — разложение квадратичной иррациональности в непрерывную дробь периодично (теорема Лагранжа). Поэтому количество соотношений, которые можно получить с помощью данного метода, ограниченно, и их может оказаться недостаточно для набора соотношений и построения сравнения [math]\displaystyle{ x^2 \equiv y^2 \pmod m }[/math]. При этом, как показывают практические эксперименты, при больших значениях [math]\displaystyle{ m }[/math] длина периода разложения в непрерывную дробь оказывается достаточно большой (порядка [math]\displaystyle{ \sqrt{m} }[/math] [10]) для составления требуемого числа сравнений. В результате при больших [math]\displaystyle{ m }[/math] оба варианта алгоритма всегда находят разложение числа [math]\displaystyle{ m }[/math] на множители[11].
Первый вариант
Напомним, что каждому действительному числу [math]\displaystyle{ \xi }[/math] может быть поставлена в соответствие последовательность целых чисел [math]\displaystyle{ [b_0 , b_1 , b_2 , . . . ] }[/math], называемая его непрерывной дробью. Это сопоставление строится следующим образом
- [math]\displaystyle{ x_0 = \xi,\quad b_i = [x_i],\quad x_{i+1} = \frac{1}{x_i - b_i},\quad i = 0,1,2,\dots . }[/math]
При этом [math]\displaystyle{ \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 ]. }[/math]
Если раскладывать в непрерывную дробь число [math]\displaystyle{ \xi = \sqrt{m} }[/math], то возникающие в процессе разложения числа [math]\displaystyle{ x_n }[/math] имеют вид [math]\displaystyle{ x_n = \frac{\sqrt{m} + A_n}{B_n} }[/math] с целыми [math]\displaystyle{ A_n, B_n }[/math], причем выполняется [math]\displaystyle{ A_n \lt \sqrt{m} }[/math], [math]\displaystyle{ 0 \lt B_n \lt 2 \sqrt{m} }[/math][12].
Для коэффициентов [math]\displaystyle{ A_n, B_n }[/math] выполняется равенство[3]:
- [math]\displaystyle{ A_n^2 + B_n B_{n-1} = m. }[/math]
Отсюда следует
- [math]\displaystyle{ -B_n B_{n-1} \equiv A_n^2 \pmod m,\quad n = 0,1, \dots\ .\quad\quad\quad\quad (1) }[/math]
Полученное равенство имеет вид [math]\displaystyle{ u^2 \equiv \upsilon \pmod m }[/math], предложенный Крайчиком, и может быть применено для факторизации числа [math]\displaystyle{ m }[/math].
Вычисляя последовательно частные [math]\displaystyle{ A_0,B_0, A_1, B_1, \dots }[/math], будем получать выражения вида [math]\displaystyle{ (1) }[/math] для различных [math]\displaystyle{ n }[/math]. Раскладывая величины [math]\displaystyle{ B_n }[/math] на простые множители и комбинируя полученные равенства, можно получить сравнения вида [math]\displaystyle{ x^2 \equiv y^2 \pmod m }[/math] (см. #пример1).
Второй вариант
С каждой непрерывной дробью свяжем последовательность рациональных чисел, состоящую из подходящих дробей [math]\displaystyle{ \frac{P_n}{Q_n} = [b_0, b_1, \dots , b_{n-1}, b_n], n \gt 0 }[/math], вычисляемых по формулам[3]:
- [math]\displaystyle{ 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, }[/math]
- [math]\displaystyle{ P_0 = b_0,\quad Q_0 = P_{-1} = 1, \quad Q_{-1} = 0 }[/math]
и стремящихся к разлагаемому числу. Если в непрерывную дробь разлагается число [math]\displaystyle{ \xi =\sqrt{m} }[/math], то справедливо соотношение[12]:
- [math]\displaystyle{ P^2_{n-1} - m Q_{n-1}= (-1)^n B_n }[/math] ,
из которого следует
- [math]\displaystyle{ P^2_{n-1} \equiv (-1)^n B_n \pmod m, n = 1,2, \dots \ . \quad\quad\quad\quad (2) }[/math]
Полученное равенство имеет вид [math]\displaystyle{ u^2 \equiv \upsilon \pmod m }[/math] и может быть использовано для факторизации числа [math]\displaystyle{ m }[/math] так же, как и в первом варианте.
Алгоритм
Таким образом, исправленный Лемером и Пауэрсом метод Крайчика имеет следующий вид[13].
Вход. Составное число [math]\displaystyle{ m }[/math].
Выход. Нетривиальный делитель [math]\displaystyle{ p }[/math] числа [math]\displaystyle{ m }[/math].
- Разложить [math]\displaystyle{ \sqrt{m} }[/math] в непрерывную дробь.
- Используя равенства [math]\displaystyle{ (1) }[/math] или [math]\displaystyle{ (2) }[/math], получить множество сравнений вида [math]\displaystyle{ u^2 \equiv \upsilon \pmod m }[/math] и разложить числа [math]\displaystyle{ \upsilon }[/math] на простые множители.
- Выбрать те равенства [math]\displaystyle{ u^2 \equiv \upsilon \pmod m }[/math], перемножение которых даст произведение четных степеней простых чисел, полученных в результате разложения чисел [math]\displaystyle{ \upsilon }[/math]. Тем самым, мы получим соотношение вида [math]\displaystyle{ x^2 \equiv y^2 \pmod m }[/math].
- Если [math]\displaystyle{ x \equiv \pm y \pmod m }[/math], то вернуться на шаг 3. Если имеющегося числа соотношений недостаточно для генерации равенства [math]\displaystyle{ x^2 \equiv y^2 \pmod m }[/math], то необходимо продолжить разложение числа [math]\displaystyle{ \sqrt{m} }[/math] в непрерывную дробь и, затем, вернуться на шаг 2.
- С помощью алгоритма Евклида определить [math]\displaystyle{ p = \gcd (x - y,m) }[/math].
Лемер и Пауэрс в своей работе указали, как можно генерировать соотношения вида [math]\displaystyle{ u^2 \equiv \upsilon \pmod m }[/math], однако они, также как и Крайчик, не дали алгоритмического способа составления из найденных соотношений сравнения [math]\displaystyle{ x^2 \equiv y^2 \pmod m }[/math]. Эту проблему решил метод Моррисона и Бриллхарта.
Метод Моррисона и Бриллхарта
В начале 1970-х годов в статье[5] Майкл Моррисон и Джон Бриллхарт предложили свой алгоритм, являющийся модификацией второго варианта алгоритма Лемера и Пауэрса. В настоящее время под методом непрерывных дробей понимают именно алгоритм Моррисона и Бриллхарта.
Основное отличие реализованного Моррисоном и Бриллхартом алгоритма от первоначального варианта заключалось в введении процедуры алгоритмического построения сравнения [math]\displaystyle{ x^2 \equiv y^2 \pmod m }[/math] по заданному множеству сравнений вида [math]\displaystyle{ u^2 \equiv \upsilon \pmod m }[/math]. Для реализации этой процедуры использовалось понятие «факторной базы»[11].
Будем искать [math]\displaystyle{ x }[/math] как произведение таких чисел [math]\displaystyle{ u_i }[/math], что наименьший по абсолютной величине вычет числа [math]\displaystyle{ u_i^2 }[/math] по модулю [math]\displaystyle{ m }[/math] является произведением простых чисел[14]. Тогда из тех же простых чисел можно построить и [math]\displaystyle{ y }[/math].
Базой факторизации (или факторной базой) натурального числа [math]\displaystyle{ m }[/math] называется множество [math]\displaystyle{ B = \{ p_0, p_1, \dots, p_h \} }[/math] различных простых чисел [math]\displaystyle{ p_i }[/math], за возможным исключением [math]\displaystyle{ p_0 }[/math], которое может быть равным [math]\displaystyle{ - 1 }[/math]. При этом число [math]\displaystyle{ b }[/math], для которого [math]\displaystyle{ b^2\bmod m }[/math] является произведением степеней чисел из множества [math]\displaystyle{ B }[/math], называется B-гладким числом. Пусть теперь [math]\displaystyle{ u_i }[/math] — B-гладкие числа, [math]\displaystyle{ \upsilon_i = u_i^2\bmod m = \prod_{j=0}^h p_j^{\alpha_{ij}} }[/math] — разложения их наименьшие по абсолютной величине вычетов по модулю [math]\displaystyle{ m }[/math]. Положим
- [math]\displaystyle{ \mathbf{e}_i = (e_{i0}, e_{i1}, \dots, e_{ih}) \in \mathbb{F}^h_2 }[/math],
где [math]\displaystyle{ e_{ij} \equiv \alpha_{ij} \mod 2 }[/math], [math]\displaystyle{ \mathbb{F}^h_2 }[/math] — векторное пространство над полем GF(2), которое состоит из наборов нулей и единиц размерности [math]\displaystyle{ h }[/math].
Подберем числа [math]\displaystyle{ u_i }[/math] так, чтобы сумма векторов [math]\displaystyle{ \mathbf{e}_i }[/math] была равна нулю. Определим
- [math]\displaystyle{ x = \left(\prod_i u_i\right) \bmod m, \quad y = \prod_{j=0}^h p_j^{\gamma_j} }[/math],
где [math]\displaystyle{ \gamma_j = \frac{1}{2} \sum_i \alpha_{ij} }[/math]. Тогда [math]\displaystyle{ x^2 \equiv y^2 \pmod m }[/math].
Осталось добавить, что факторная база в алгоритме Моррисона и Бриллхарта состоит из тех простых чисел [math]\displaystyle{ p_i }[/math], по модулю которых [math]\displaystyle{ m }[/math] является квадратичным вычетом[15].
Алгоритм
Алгоритм Моррисона и Бриллхарта выглядит следующим образом[16].
Вход. Составное число [math]\displaystyle{ m }[/math].
Выход. Нетривиальный делитель [math]\displaystyle{ p }[/math] числа [math]\displaystyle{ m }[/math].
1. Построить базу разложения [math]\displaystyle{ B = \{p_0, p_1, \dots, p_h\} }[/math], где [math]\displaystyle{ p_0=-1 }[/math] и [math]\displaystyle{ p_1, \dots, p_h }[/math] — попарно различные простые числа, по модулю которых [math]\displaystyle{ m }[/math] является квадратичным вычетом.
2. Берутся целые числа [math]\displaystyle{ u_i }[/math], являющиеся числителями подходящих дробей к обыкновенной непрерывной дроби, выражающей число [math]\displaystyle{ \sqrt{m} }[/math]. Из этих числителей выбираются [math]\displaystyle{ h+2 }[/math] чисел, для которых абсолютно наименьшие вычеты [math]\displaystyle{ u_i^2 }[/math] по модулю [math]\displaystyle{ m }[/math] являются B-гладкими:
- [math]\displaystyle{ u_i^2 \bmod m = \prod^h_{j=0}p_j^{\alpha_{ij}} = \upsilon_i }[/math],
где [math]\displaystyle{ \alpha_{ij} \geqslant 0 }[/math]. Также каждому числу [math]\displaystyle{ u_i }[/math] сопоставляется вектор показателей [math]\displaystyle{ (\alpha_{i0}, \alpha_{i1}, \dots, \alpha_{ih}) }[/math].
3. Найти (например, методом Гаусса) такое непустое множество [math]\displaystyle{ K \subseteqq \{1, 2, \dots, h+1\} }[/math], что [math]\displaystyle{ \oplus_{i \in K}\mathbf{e}_i = 0 }[/math], где [math]\displaystyle{ \oplus }[/math] — операция исключающее ИЛИ, [math]\displaystyle{ \mathbf{e}_i = (e_{i1}, e_{i2}, \dots, e_{ih} ), e_{ij} \equiv \alpha_{ij} \pmod 2 }[/math], [math]\displaystyle{ 0 \leqslant j \leqslant h }[/math].
4. Положить [math]\displaystyle{ 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 }[/math]. Тогда [math]\displaystyle{ x^2 \equiv y^2 \pmod m }[/math].
5. Если [math]\displaystyle{ x \not\equiv y \pmod m }[/math], то положить [math]\displaystyle{ p \leftarrow \gcd(x - y, m) }[/math] и выдать результат: [math]\displaystyle{ p }[/math].
- В противном случае вернуться на шаг 3 и поменять множество [math]\displaystyle{ K }[/math]. (Обычно есть несколько вариантов выбора множества [math]\displaystyle{ K }[/math] для одной и той же факторной базы [math]\displaystyle{ B }[/math]. Если все возможности исчерпаны, то следует увеличить размер факторной базы).
Из полученного алгоритма впоследствии был разработан алгоритм Диксона, из которого был удален аппарат цепных дробей[17]. После создания алгоритма Диксона, метод непрерывных дробей, по сути, представлял собой алгоритм Диксона, в котором был уточнен выбор абсолютно наименьшего вычета [math]\displaystyle{ u_i }[/math][18].
Некоторые улучшения
Пусть [math]\displaystyle{ m = p\cdot q }[/math]. Выше в непрерывную дробь раскладывалось число [math]\displaystyle{ \sqrt{m} }[/math]. Такой вариант эффективен, когда [math]\displaystyle{ p }[/math] и [math]\displaystyle{ q }[/math] близки друг к другу. Однако, чем больше разность между числами [math]\displaystyle{ p }[/math] и [math]\displaystyle{ q }[/math], тем более трудоемким становится алгоритм. В этом случае вместо [math]\displaystyle{ \sqrt{m} }[/math] можно раскладывать в непрерывную дробь число [math]\displaystyle{ \sqrt{km} }[/math] , где маленький множитель [math]\displaystyle{ k }[/math] подбирается так, чтобы в базу множителей вошли все малые простые[19].
Кроме того, так как метод непрерывных дробей построен по схеме алгоритма Диксона, то для него применимы дополнительные стратегии алгоритма Диксона.
Обоснование
Следующая лемма показывает, что если выполнено сравнение [math]\displaystyle{ x^2 \equiv y^2 \pmod m }[/math] и [math]\displaystyle{ x \not \equiv y \pmod m }[/math], то числа [math]\displaystyle{ x - y }[/math] и [math]\displaystyle{ m }[/math] имеют общие делители.
Лемма(о факторизации)[20]. Пусть [math]\displaystyle{ m }[/math] — нечётное составное число и [math]\displaystyle{ x,y }[/math] — вычеты по модулю [math]\displaystyle{ m }[/math] такие, что [math]\displaystyle{ x \not \equiv \pm y \pmod m }[/math] и [math]\displaystyle{ x^2 \equiv y^2 \pmod m }[/math]. Тогда выполняется неравенство [math]\displaystyle{ 1 \lt \gcd (x - y, m) \lt m }[/math].
Следующие два утверждения — ключевые для алгоритма факторизации методом непрерывных дробей. Они показывают, что можно найти последовательность чисел [math]\displaystyle{ u_i }[/math], квадраты которых имеют малые вычеты по модулю [math]\displaystyle{ m }[/math].
Теорема[21]. Если [math]\displaystyle{ \frac{P_n}{Q_n} }[/math], где [math]\displaystyle{ n = 1, 2, \dots }[/math], — подходящие дроби к числу [math]\displaystyle{ \alpha \gt 1 }[/math], которое задано обыкновенной непрерывной дробью, то для всех [math]\displaystyle{ n }[/math] справедлива оценка [math]\displaystyle{ |P_n^2 - \alpha ^2 Q_n^2| \lt 2 \alpha }[/math].
Следствие[21]. Пусть положительное число [math]\displaystyle{ m }[/math] не является полным квадратом и [math]\displaystyle{ \frac{P_n}{Q_n} }[/math], где [math]\displaystyle{ n = 1, 2, \dots }[/math], — подходящие дроби к числу [math]\displaystyle{ \sqrt{m} }[/math]. Тогда для абсолютно наименьшего вычета [math]\displaystyle{ P^2_n \bmod m }[/math] (т.е. для вычета, расположенного между [math]\displaystyle{ -\frac{m}{2} }[/math] и [math]\displaystyle{ \frac{m}{2} }[/math]) справедливо неравенство [math]\displaystyle{ |P_n^2 \bmod m | \lt 2 \sqrt{m} }[/math], причем [math]\displaystyle{ P_n^2 \bmod m = P_n^2 - m Q^2_n }[/math].
Примеры
- Пример 1[22]
Разложим на множители первым алгоримом Лемера и Пауэрса число [math]\displaystyle{ m = 1081 }[/math].
1. Будем раскладывать число [math]\displaystyle{ \xi = \sqrt{m} = \sqrt{1081} }[/math] в непрерывную дробь и записывать числа [math]\displaystyle{ A_n, B_n }[/math] в таблицу для получения уравнений вида [math]\displaystyle{ u^2 \equiv \upsilon \pmod m }[/math].
i | xi | Ai | Bi |
---|---|---|---|
1 | [math]\displaystyle{ \frac{32 + \sqrt{1081}}{57} }[/math] | 32 | 57 |
2 | [math]\displaystyle{ \frac{25 + \sqrt{1081}}{8} }[/math] | 25 | 8 |
3 | [math]\displaystyle{ \frac{31 + \sqrt{1081}}{15} }[/math] | 31 | 15 |
4 | [math]\displaystyle{ \frac{29 + \sqrt{1081}}{16} }[/math] | 29 | 16 |
5 | [math]\displaystyle{ \frac{19 + \sqrt{1081}}{45} }[/math] | 19 | 45 |
6 | [math]\displaystyle{ \frac{26 + \sqrt{1081}}{9} }[/math] | 26 | 9 |
2. Теперь запишем сравнения [math]\displaystyle{ -B_n B_{n-1} \equiv A^2_n \pmod m }[/math] для [math]\displaystyle{ n = 2, 3, 4, 5, 6 }[/math]:
- [math]\displaystyle{ -2^3 \cdot 3 \cdot 19 \equiv 25^2 \pmod{1081}, }[/math]
- [math]\displaystyle{ -2^3 \cdot 3 \cdot 5 \equiv 31^2 \pmod{1081}, }[/math]
- [math]\displaystyle{ -2^4 \cdot 3 \cdot 5 \equiv 29^2 \pmod{1081}, }[/math]
- [math]\displaystyle{ -2^4 \cdot 3^2 \cdot 5 \equiv 19^2 \pmod{1081}, }[/math]
- [math]\displaystyle{ -3^4 \cdot 5 \equiv 26^2 \pmod{1081}. }[/math]
3. Перемножая четвертое и пятое сравнения, получим:
- [math]\displaystyle{ (-1)^2 \cdot 2^4 \cdot 3^2 \cdot 5 \cdot 3^4 \cdot 5 \equiv 19^2 \cdot 26^2 \pmod{1081}, }[/math]
и, приводя подобные множители и сокращая на [math]\displaystyle{ 3^2 }[/math]:
- [math]\displaystyle{ 2^4 \cdot 3^6 \cdot 5^2 \equiv 19^2 \cdot 26^2 \pmod{1081} }[/math] или [math]\displaystyle{ 540^2 \equiv 494^2 \pmod{1081}. }[/math]
4. Получили сравнение вида [math]\displaystyle{ x^2 \equiv y^2 \pmod m }[/math], используя которое можно найти делитель числа 1081. Действительно, [math]\displaystyle{ \gcd (540 - 494, 1081) = 23 }[/math]. Тогда, второй делитель числа 1081 равен 47.
- Пример 2[23]
Разложим на множители методом Морриса и Брилхарта число [math]\displaystyle{ m = 21299881 }[/math].
1. Строим базу разложения из маленьких простых чисел, выбирая числа, по модулю которых [math]\displaystyle{ m }[/math] является квадратичным вычетом, что проверяется вычислением символов Лежандра:
- [math]\displaystyle{ \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. }[/math]
Отсюда, факторная база будет равна [math]\displaystyle{ B = \{-1, 2, 3, 5, 7, 11, 19\} }[/math], [math]\displaystyle{ h = 6 }[/math].
2. Ищем числители [math]\displaystyle{ P_i }[/math] подходящих дробей к числу [math]\displaystyle{ \sqrt{m} }[/math]:
- [math]\displaystyle{ \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 }]. }[/math]
Выбираем те из них, для которых значения [math]\displaystyle{ P_i^2 \bmod m }[/math] являются B-гладкими. Результаты вычислений записываем в таблицу:
k | i | Pi | P2i [math]\displaystyle{ \pmod m }[/math] | ei |
---|---|---|---|---|
1 | 2 | 27691 | [math]\displaystyle{ -4235 = -1 \cdot 5 \cdot 7 \cdot 11^2 }[/math] | (1, 0, 0, 1, 1, 0, 0) |
2 | 3 | 50767 | [math]\displaystyle{ 2688 = 2^7 \cdot 3 \cdot 7 }[/math] | (0, 1, 1, 0, 1, 0, 0) |
3 | 6 | 1389169 | [math]\displaystyle{ -7920 = -1 \cdot 2^4 \cdot 3^2 \cdot 5 \cdot 11 }[/math] | (1, 0, 0, 1, 0, 1, 0) |
4 | 13 | 12814433311 | [math]\displaystyle{ 385 = 5 \cdot 7 \cdot 11 }[/math] | (0, 0, 0, 1, 1, 1, 0) |
5 | 16 | 2764443209657 | [math]\displaystyle{ -3800 = -1 \cdot 2^3 \cdot 5^2 \cdot 19 }[/math] | (1, 1, 0, 0, 0, 0, 1) |
6 | 18 | 20276855015255 | [math]\displaystyle{ -1331 = -1 \cdot 11^3 }[/math] | (1, 0, 0, 0, 0, 1, 0) |
7 | 19 | 127498600693396 | [math]\displaystyle{ 5415 = 3 \cdot 5 \cdot 19^2 }[/math] | (0, 0, 1, 1, 0, 0, 0) |
8 | 24 | 2390521616955537 | [math]\displaystyle{ -112 = -1 \cdot 2^4 \cdot 7 }[/math] | (1, 0, 0, 0, 1, 0, 0) |
3. Поскольку [math]\displaystyle{ e_1 \oplus e_3 \oplus e_6 \oplus e_8 = 0 }[/math], то получаем
4. [math]\displaystyle{ x = P_2 \cdot P_6 \cdot P_{18} \cdot P_{24} \equiv 12487442 \pmod m }[/math],
- [math]\displaystyle{ y = 2^4 \cdot 3^1 \cdot 5^1 \cdot 7^1 \cdot 11^3 \cdot 19^0 = 2236080 }[/math],
- [math]\displaystyle{ x^2 \equiv y^2 \equiv 13201055 \pmod m }[/math].
5. Условие [math]\displaystyle{ x \not \equiv \pm y \pmod m }[/math] выполнено, поэтому вычисляем [math]\displaystyle{ p = \gcd (x - y, m) = \gcd (10251362, 21299881 ) = 3851 }[/math].
Поэтому, [math]\displaystyle{ 21299881 = 3851 \cdot 5531 }[/math].
Вычислительная сложность
С появлением криптосистемы RSA в конце 1970-х годов стала особенно важна вычислительная сложность алгоритмов факторизации[2].
Эвристический анализ времени выполнения алгоритма Морриса и Брилхарта был проведен Р. Шруппелем в 1975 году, хотя не был опубликован[24][2].
Более точная оценка(которая при этом все равно оставалась эвристической) была проведена в работе[25]. Приведем результаты оценки сложности в соответствии с этой работой.
При получении оценок в этой работе делаются некоторые эвристические допущения. Например, предполагают, что если помощью алгоритма построено [math]\displaystyle{ 1 + [\log^2 m] }[/math] пар [math]\displaystyle{ (x, y) }[/math] таких, что [math]\displaystyle{ x^2 \equiv y^2 \pmod m }[/math], то хотя бы для одной из них выполнены неравенства
- [math]\displaystyle{ 1 \lt \gcd (x \pm y, m) }[/math].
Утверждение[26]. Если [math]\displaystyle{ a = \frac{1}{\sqrt{2}} }[/math], [math]\displaystyle{ L = L(m) = \exp((\log m \log \log m)^{1/2} ) }[/math] и факторная база состоит из [math]\displaystyle{ p = -1 }[/math] и всех простых чисел [math]\displaystyle{ p }[/math] таких, что:
- [math]\displaystyle{ 2 \leqslant p \leqslant L^a, \quad \left ( \frac{m}{p} \right ) = +1 }[/math],
то при вычислении [math]\displaystyle{ L^b }[/math] подходящих дробей, где [math]\displaystyle{ b = a + \frac{1}{4a} }[/math], можно ожидать, что алгоритм разложит [math]\displaystyle{ m }[/math] на два множителя с эвристической оценкой сложности [math]\displaystyle{ L_m\left [ \frac{1}{2}; 2\right ] }[/math] арифметических операций.
См. также
- Факторизация
- Факторизация целых чисел
- Непрерывная дробь
- Метод факторизации Ферма
- Алгоритм Диксона
- Метод квадратичного решета
Примечания
- ↑ Кнут, 2013, pp. 439,441.
- ↑ 2,0 2,1 2,2 2,3 2,4 2,5 2,6 2,7 Pomerance, 1996.
- ↑ 3,0 3,1 3,2 3,3 3,4 Lehmer, Powers, 1931.
- ↑ 4,0 4,1 Кнут, 2013, pp. 434.
- ↑ 5,0 5,1 Morrison, Brillhart, 1975.
- ↑ Маховенко, 2006, pp. 223.
- ↑ Kraitchik M. Théorie des Nombres. Tome I et II. — Paris:Gauthier-Villars. — 1926.
- ↑ 8,0 8,1 Нестеренко, 2012, pp. 173.
- ↑ Нестеренко, 2012, pp. 175.
- ↑ Ященко, 1999, pp. 113.
- ↑ 11,0 11,1 Нестеренко, 2012, pp. 178.
- ↑ 12,0 12,1 Ященко, 1999, pp. 112-113.
- ↑ Нестеренко, 2012, pp. 173,185.
- ↑ Манин, 1990, pp. 78.
- ↑ Маховенко, 2006, pp. 220.
- ↑ Маховенко, 2006, pp. 218-220.
- ↑ Кнут, 2013, pp. 439.
- ↑ Маховенко, 2006, pp. 219.
- ↑ Ященко, 1999, pp. 114.
- ↑ Нестеренко, 2012, pp. 172.
- ↑ 21,0 21,1 Маховенко, 2006, pp. 219-220.
- ↑ Нестеренко, 2012, pp. 176-177.
- ↑ Маховенко, 2006, pp. 221-222.
- ↑ Кнут, 2013, pp. 436.
- ↑ Pomerance, 1982.
- ↑ Василенко, 2003, pp. 87.
Литература
- Шаблон:Source
- Шаблон:Source
- Шаблон:Source
- Манин, Ю. И., Панчишкин, А. А. Глава 3.4. Метод непрерывных дробей (CFRAC) и вещественные квадратичные поля // Введение в теорию чисел, Теория чисел – 1. — Итоги науки и техн. Сер. Соврем. пробл. мат. Фундам. направления. — М.: ВИНИТИ, 1990. — Т. 49. — С. 77-80. — 341 с.
- Шаблон:Source
- Введение в криптографию / Ященко, В. В.. — Москва: МЦНМО, 1999. — 272 с. — ISBN 5-900916-40-5.
- Шаблон:Source
- Шаблон:Source
- Шаблон:Source
- Шаблон:Source
- Шаблон:Source