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

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

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

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

История

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

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

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

${\displaystyle 2^{2^{7}}+1=59649589127497217\cdot 5704689200685129054721.}$

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

Описание алгоритма

Метод Лемера и Пауэрса

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

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

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

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

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

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

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

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

Действительно, рассмотрим последовательность чисел вида ${\displaystyle \upsilon (u)=u^{2}-m}$ (очевидно, ${\displaystyle \upsilon \equiv u^{2}{\pmod {m}}}$). Тогда, если ${\displaystyle \upsilon (u_{1})\upsilon (u_{2})\dots \upsilon (u_{k})=y^{2}}$, т.е. ${\displaystyle (u_{1}^{2}-m)(u_{2}^{2}-m)\dots (u_{k}^{2}-m)=y^{2}}$, то отсюда следует, что ${\displaystyle x^{2}=u_{1}^{2}u_{2}^{2}\dots u_{k}^{2}\equiv y^{2}{\pmod {m}}}$^[2]. Для того, чтобы определить, какие именно соотношения нужно перемножить, необходимо раскладывать числа ${\displaystyle \upsilon }$ на множители и перемножать соотношения так, чтобы в произведениях ${\displaystyle \upsilon _{1}\upsilon _{2}\dots \upsilon _{k}}$ присутствовали простые множители в четных степенях, позволяющие получить сравнение ${\displaystyle x^{2}\equiv y^{2}{\pmod {m}}}$^[8].

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

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

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

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

Первый вариант

Напомним, что каждому действительному числу ${\displaystyle \xi }$ может быть поставлена в соответствие последовательность целых чисел ${\displaystyle [b_{0},b_{1},b_{2},...]}$, называемая его непрерывной дробью. Это сопоставление строится следующим образом

${\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 .}$

При этом ${\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}].}$

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

Для коэффициентов ${\displaystyle A_{n},B_{n}}$ выполняется равенство^[3]:

${\displaystyle A_{n}^{2}+B_{n}B_{n-1}=m.}$

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

${\displaystyle -B_{n}B_{n-1}\equiv A_{n}^{2}{\pmod {m}},\quad n=0,1,\dots \ .\quad \quad \quad \quad (1)}$

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

Вычисляя последовательно частные ${\displaystyle A_{0},B_{0},A_{1},B_{1},\dots }$, будем получать выражения вида ${\displaystyle (1)}$ для различных ${\displaystyle n}$. Раскладывая величины ${\displaystyle B_{n}}$ на простые множители и комбинируя полученные равенства, можно получить сравнения вида ${\displaystyle x^{2}\equiv y^{2}{\pmod {m}}}$ (см. #пример1).

Второй вариант

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

${\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,}$

${\displaystyle P_{0}=b_{0},\quad Q_{0}=P_{-1}=1,\quad Q_{-1}=0}$

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

${\displaystyle P_{n-1}^{2}-mQ_{n-1}=(-1)^{n}B_{n}}$ ,

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

${\displaystyle P_{n-1}^{2}\equiv (-1)^{n}B_{n}{\pmod {m}},n=1,2,\dots \ .\quad \quad \quad \quad (2)}$

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

Алгоритм

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

Вход. Составное число ${\displaystyle m}$.

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

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

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

Метод Моррисона и Бриллхарта

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

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

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

Базой факторизации (или факторной базой) натурального числа ${\displaystyle m}$ называется множество ${\displaystyle B=\{p_{0},p_{1},\dots ,p_{h}\}}$ различных простых чисел ${\displaystyle p_{i}}$, за возможным исключением ${\displaystyle p_{0}}$, которое может быть равным ${\displaystyle -1}$. При этом число ${\displaystyle b}$, для которого ${\displaystyle b^{2}{\bmod {m}}}$ является произведением степеней чисел из множества ${\displaystyle B}$, называется B-гладким числом. Пусть теперь ${\displaystyle u_{i}}$ — B-гладкие числа, ${\displaystyle \upsilon _{i}=u_{i}^{2}{\bmod {m}}=\prod _{j=0}^{h}p_{j}^{\alpha _{ij}}}$ — разложения их наименьшие по абсолютной величине вычетов по модулю ${\displaystyle m}$. Положим

${\displaystyle \mathbf {e} _{i}=(e_{i0},e_{i1},\dots ,e_{ih})\in \mathbb {F} _{2}^{h}}$,

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

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

${\displaystyle x=\left(\prod _{i}u_{i}\right){\bmod {m}},\quad y=\prod _{j=0}^{h}p_{j}^{\gamma _{j}}}$,

где ${\displaystyle \gamma _{j}={\frac {1}{2}}\sum _{i}\alpha _{ij}}$. Тогда ${\displaystyle x^{2}\equiv y^{2}{\pmod {m}}}$.

Осталось добавить, что факторная база в алгоритме Моррисона и Бриллхарта состоит из тех простых чисел ${\displaystyle p_{i}}$, по модулю которых ${\displaystyle m}$ является квадратичным вычетом^[15].

Алгоритм

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

Вход. Составное число ${\displaystyle m}$.

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

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

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

${\displaystyle u_{i}^{2}{\bmod {m}}=\prod _{j=0}^{h}p_{j}^{\alpha _{ij}}=\upsilon _{i}}$,

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

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

4. Положить ${\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}}}$. Тогда ${\displaystyle x^{2}\equiv y^{2}{\pmod {m}}}$.

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

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

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

Некоторые улучшения

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

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

Обоснование

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

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

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

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

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

Примеры

Пример 1^[22]

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

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

Таблица: факторизация числа 1081

i	xi	Ai	Bi
1	${\displaystyle {\frac {32+{\sqrt {1081}}}{57}}}$	32	57
2	${\displaystyle {\frac {25+{\sqrt {1081}}}{8}}}$	25	8
3	${\displaystyle {\frac {31+{\sqrt {1081}}}{15}}}$	31	15
4	${\displaystyle {\frac {29+{\sqrt {1081}}}{16}}}$	29	16
5	${\displaystyle {\frac {19+{\sqrt {1081}}}{45}}}$	19	45
6	${\displaystyle {\frac {26+{\sqrt {1081}}}{9}}}$	26	9

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

${\displaystyle -2^{3}\cdot 3\cdot 19\equiv 25^{2}{\pmod {1081}},}$

${\displaystyle -2^{3}\cdot 3\cdot 5\equiv 31^{2}{\pmod {1081}},}$

${\displaystyle -2^{4}\cdot 3\cdot 5\equiv 29^{2}{\pmod {1081}},}$

${\displaystyle -2^{4}\cdot 3^{2}\cdot 5\equiv 19^{2}{\pmod {1081}},}$

${\displaystyle -3^{4}\cdot 5\equiv 26^{2}{\pmod {1081}}.}$

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

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

и, приводя подобные множители и сокращая на ${\displaystyle 3^{2}}$:

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

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

Пример 2^[23]

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

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

${\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.}$

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

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

${\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 }].}$

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

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

3. Поскольку ${\displaystyle e_{1}\oplus e_{3}\oplus e_{6}\oplus e_{8}=0}$, то получаем

4. ${\displaystyle x=P_{2}\cdot P_{6}\cdot P_{18}\cdot P_{24}\equiv 12487442{\pmod {m}}}$,

${\displaystyle y=2^{4}\cdot 3^{1}\cdot 5^{1}\cdot 7^{1}\cdot 11^{3}\cdot 19^{0}=2236080}$,

${\displaystyle x^{2}\equiv y^{2}\equiv 13201055{\pmod {m}}}$.

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

Поэтому, ${\displaystyle 21299881=3851\cdot 5531}$.

Вычислительная сложность

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

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

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

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

${\displaystyle 1<\gcd(x\pm y,m)}$.

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

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

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

См. также

• Факторизация
• Факторизация целых чисел
• Непрерывная дробь
• Метод факторизации Ферма
• Алгоритм Диксона
• Метод квадратичного решета