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

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

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

История

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

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

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

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

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

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

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

В 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}$ является гладким , то метод Ферма может работать даже медленней метода пробных делений .

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

Крайчик предложил вместо пар чисел ${\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}$ (см. ).

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

Действительно, рассмотрим последовательность чисел вида ${\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}}}$ . Для того, чтобы определить, какие именно соотношения нужно перемножить, необходимо раскладывать числа ${\displaystyle \upsilon }$ на множители и перемножать соотношения так, чтобы в произведениях ${\displaystyle \upsilon _{1}\upsilon _{2}\dots \upsilon _{k}}$ присутствовали простые множители в четных степенях, позволяющие получить сравнение ${\displaystyle x^{2}\equiv y^{2}{\pmod {m}}}$ .

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

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

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

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

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

Напомним, что каждому действительному числу ${\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}}}$ .

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

${\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}}}$ (см. ).

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

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

${\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}}}$ , то справедливо соотношение :

${\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}$ так же, как и в первом варианте.

Алгоритм

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

Вход . Составное число ${\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-х годов в статье Майкл Моррисон и Джон Бриллхарт предложили свой алгоритм, являющийся модификацией второго варианта алгоритма Лемера и Пауэрса. В настоящее время под методом непрерывных дробей понимают именно алгоритм Моррисона и Бриллхарта.

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

Будем искать ${\displaystyle x}$ как произведение таких чисел ${\displaystyle u_{i}}$ , что наименьший по абсолютной величине вычет числа ${\displaystyle u_{i}^{2}}$ по модулю ${\displaystyle m}$ является произведением простых чисел . Тогда из тех же простых чисел можно построить и ${\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}$ является квадратичным вычетом .

Алгоритм

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

Вход . Составное число ${\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}$ . Если все возможности исчерпаны, то следует увеличить размер факторной базы).

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

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

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

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

Обоснование

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

Лемма (о факторизации) . Пусть ${\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}$ .

Теорема . Если ${\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 }$ .

Следствие . Пусть положительное число ${\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

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

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

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

i	x i	A i	B i
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

Разложим на множители методом Морриса и Брилхарта число ${\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	P i	P 2 i ${\displaystyle {\pmod {m}}}$	e i
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-х годов стала особенно важна вычислительная сложность алгоритмов факторизации .

Эвристический анализ времени выполнения алгоритма Морриса и Брилхарта был проведен _en в 1975 году , хотя не был опубликован .

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

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

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

Утверждение . Если ${\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]}$ арифметических операций .

См. также

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

Примечания

Литература

• Lehmer D. H. , (англ.) // Bulletin (new series) of the American Mathematical Society. / — Providence: American Mathematical Society , 1931. — Vol. 33, Iss. 1. — P. 35—36. — ISSN ; —
• , (англ.) // — AMS , 1975. — Vol. 29, Iss. 129. — P. 183—205. — ISSN ; —
• Pomerance C. (англ.) // : Part I / H. Lenstra , — Amsterdam: Mathematisch Centrum , 1982. — P. 89—139.
• Манин, Ю. И., Панчишкин, А. А. Глава 3.4. Метод непрерывных дробей (CFRAC) и вещественные квадратичные поля // . — Итоги науки и техн. Сер. Соврем. пробл. мат. Фундам. направления. — М. : ВИНИТИ , 1990. — Т. 49. — С. 77-80. — 341 с.
• Pomerance C. (англ.) // Notices of the American Mathematical Society / — AMS , 1996. — Vol. 43. — P. 1473—1485. — ISSN ;
• Введение в криптографию / Ященко, В. В.. — Москва: МЦНМО , 1999. — 272 с. — ISBN 5-900916-40-5 .
• Коблиц Н. — 2-е издание — М. : , 2001. — С. 174—179. — 254 с. — ISBN 978-5-85484-014-9 , 978-5-85484-012-5
• — М. : МЦНМО , 2003. — 328 с. — ISBN 978-5-94057-103-2
• — М. : , 2006. — С. 219—222. — ISBN 978-5-85438-143-7
• — М. : Московский государственный институт электроники и математики , 2012. — С. 172—186. — 224 с. — ISBN 978-5-94506-320-4
• Кнут Д. Э. — 3-е издание — , 2013. — Т. 2. Получисленные алгоритмы. — 832 с. — ISBN 978-5-8459-0081-4