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

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

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

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

ИсторияПравить

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

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

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

$2^{2^7}+1=59649589127497217\cdot <!--\; \cdot \; -->5704689200685129054721.$$2^{2^{7}}+1=59649589127497217\cdot 5704689200685129054721.$ 

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

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

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

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

$ab={\left(\frac{a+b}{2}\right)}^2-<!--\; -\; -->{\left(\frac{a-<!--\; -\; -->b}{2}\right)}^2=x^2-<!--\; -\; -->y^2=m$$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={\frac {a+b}{2}},\quad y={\frac {a-b}{2}}$ .

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

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

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

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

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

Действительно, рассмотрим последовательность чисел вида $\mathrm{\upsilon <!--\; \upsilon \; -->}(u)=u^2-<!--\; -\; -->m$$\upsilon (u)=u^{2}-m$  (очевидно, $\mathrm{\upsilon <!--\; \upsilon \; -->}\equiv <!--\; \equiv \; -->u^2(\mathrm{mod}m)$$\upsilon \equiv u^{2}{\pmod {m}}$ ). Тогда, если $\mathrm{\upsilon <!--\; \upsilon \; -->}(u_1)\mathrm{\upsilon <!--\; \upsilon \; -->}(u_2)\dots <!--\; \dots \; -->\mathrm{\upsilon <!--\; \upsilon \; -->}(u_k)=y^2$$\upsilon (u_{1})\upsilon (u_{2})\dots \upsilon (u_{k})=y^{2}$ , т.е. $(u_1^2-<!--\; -\; -->m)(u_2^2-<!--\; -\; -->m)\dots <!--\; \dots \; -->(u_k^2-<!--\; -\; -->m)=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 <!--\; \dots \; -->u_k^2\equiv <!--\; \equiv \; -->y^2(\mathrm{mod}m)$$x^{2}=u_{1}^{2}u_{2}^{2}\dots u_{k}^{2}\equiv y^{2}{\pmod {m}}$ . Для того, чтобы определить, какие именно соотношения нужно перемножить, необходимо раскладывать числа $\mathrm{\upsilon <!--\; \upsilon \; -->}$$\upsilon$  на множители и перемножать соотношения так, чтобы в произведениях ${\mathrm{\upsilon <!--\; \upsilon \; -->}}_1{\mathrm{\upsilon <!--\; \upsilon \; -->}}_2\dots <!--\; \dots \; -->{\mathrm{\upsilon <!--\; \upsilon \; -->}}_k$$\upsilon _{1}\upsilon _{2}\dots \upsilon _{k}$  присутствовали простые множители в четных степенях, позволяющие получить сравнение $x^2\equiv <!--\; \equiv \; -->y^2(\mathrm{mod}m)$$x^{2}\equiv y^{2}{\pmod {m}}$ .

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

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

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

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

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

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

$x_0=\mathrm{\xi <!--\; \xi \; -->},b_i=[x_i],x_{i+1}=\frac{1}{x_i-<!--\; -\; -->b_i},i=0,1,2,\dots <!--\; \dots \; -->.$$x_{0}=\xi ,\quad b_{i}=[x_{i}],\quad x_{i+1}={\frac {1}{x_{i}-b_{i}}},\quad i=0,1,2,\dots .$ 

При этом $\mathrm{\xi <!--\; \xi \; -->}=b_0+\frac{1}{b_1+\frac{1}{b_2+\frac{1}{\cdots <!--\; \cdots \; -->+\frac{1}{x_n}}}}=[b_0,b_1,b_2,\dots <!--\; \dots \; -->,b_{n-<!--\; -\; -->1},x_n].$$\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}].$ 

Если раскладывать в непрерывную дробь число $\mathrm{\xi <!--\; \xi \; -->}=\sqrt{m}$$\xi ={\sqrt {m}}$ , то возникающие в процессе разложения числа $x_n$$x_{n}$  имеют вид $x_n=\frac{\sqrt{m}+A_n}{B_n}$$x_{n}={\frac {{\sqrt {m}}+A_{n}}{B_{n}}}$  с целыми $A_n,B_n$$A_{n},B_{n}$ , причем выполняется $A_{n}<{\sqrt {m}}$ , $0<B_{n}<2{\sqrt {m}}$ .

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

$A_n^2+B_n{B}_{n-<!--\; -\; -->1}=m.$$A_{n}^{2}+B_{n}B_{n-1}=m.$ 

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

$-<!--\; -\; -->B_n{B}_{n-<!--\; -\; -->1}\equiv <!--\; \equiv \; -->A_n^2(\mathrm{mod}m),n=0,1,\dots <!--\; \dots \; -->.(1)$$-B_{n}B_{n-1}\equiv A_{n}^{2}{\pmod {m}},\quad n=0,1,\dots \ .\quad \quad \quad \quad (1)$ 

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

Вычисляя последовательно частные $A_0,B_0,A_1,B_1,\dots <!--\; \dots \; -->$$A_{0},B_{0},A_{1},B_{1},\dots$ , будем получать выражения вида $(1)$$(1)$  для различных $n$$n$ . Раскладывая величины $B_n$$B_{n}$  на простые множители и комбинируя полученные равенства, можно получить сравнения вида $x^2\equiv <!--\; \equiv \; -->y^2(\mathrm{mod}m)$$x^{2}\equiv y^{2}{\pmod {m}}$  (см. #пример1).

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

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

$P_{n+1}=b_{n+1}{P}_n+P_{n-<!--\; -\; -->1},Q_{n+1}=b_{n+1}{Q}_n+Q_{n-<!--\; -\; -->1},n⩾<!--\; ⩾\; -->0,$$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,Q_0=P_{-<!--\; -\; -->1}=1,Q_{-<!--\; -\; -->1}=0$$P_{0}=b_{0},\quad Q_{0}=P_{-1}=1,\quad Q_{-1}=0$ 

и стремящихся к разлагаемому числу. Если в непрерывную дробь разлагается число $\mathrm{\xi <!--\; \xi \; -->}=\sqrt{m}$$\xi ={\sqrt {m}}$ , то справедливо соотношение:

$P_{n-<!--\; -\; -->1}^2-<!--\; -\; -->m{Q}_{n-<!--\; -\; -->1}=(-<!--\; -\; -->1{)}^n{B}_n$$P_{n-1}^{2}-mQ_{n-1}=(-1)^{n}B_{n}$  ,

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

$P_{n-<!--\; -\; -->1}^2\equiv <!--\; \equiv \; -->(-<!--\; -\; -->1{)}^n{B}_n(\mathrm{mod}m),n=1,2,\dots <!--\; \dots \; -->.(2)$$P_{n-1}^{2}\equiv (-1)^{n}B_{n}{\pmod {m}},n=1,2,\dots \ .\quad \quad \quad \quad (2)$ 

Полученное равенство имеет вид $u^2\equiv <!--\; \equiv \; -->\mathrm{\upsilon <!--\; \upsilon \; -->}(\mathrm{mod}m)$$u^{2}\equiv \upsilon {\pmod {m}}$  и может быть использовано для факторизации числа $m$$m$  так же, как и в первом варианте.

АлгоритмПравить

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

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

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

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

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

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

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

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

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

Базой факторизации (или факторной базой) натурального числа $m$$m$  называется множество $B=\{p_0,p_1,\dots <!--\; \dots \; -->,p_h\}$$B=\{p_{0},p_{1},\dots ,p_{h}\}$  различных простых чисел $p_i$$p_{i}$ , за возможным исключением $p_0$$p_{0}$ , которое может быть равным $-<!--\; -\; -->1$$-1$ . При этом число $b$$b$ , для которого $b^{2}modm$$b^{2}{\bmod {m}}$  является произведением степеней чисел из множества $B$$B$ , называется B-гладким числом. Пусть теперь $u_i$$u_{i}$  — B-гладкие числа, ${\mathrm{\upsilon <!--\; \upsilon \; -->}}_i=u_i^{2}modm=\underset{j=0}{\overset{h}{\prod <!--\; \prod \; -->}}{p}_j^{{\mathrm{\alpha <!--\; \alpha \; -->}}_{ij}}$$\upsilon _{i}=u_{i}^{2}{\bmod {m}}=\prod _{j=0}^{h}p_{j}^{\alpha _{ij}}$  — разложения их наименьшие по абсолютной величине вычетов по модулю $m$$m$ . Положим

${\mathbf{e}}_i=(e_{i0},e_{i1},\dots <!--\; \dots \; -->,e_{ih})\in <!--\; \in \; -->{\mathbb{F}}_2^h$$\mathbf {e} _{i}=(e_{i0},e_{i1},\dots ,e_{ih})\in \mathbb {F} _{2}^{h}$ ,

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

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

$x=\left(\underset{i}{\prod <!--\; \prod \; -->}{u}_i\right)modm,y=\underset{j=0}{\overset{h}{\prod <!--\; \prod \; -->}}{p}_j^{{\mathrm{\gamma <!--\; \gamma \; -->}}_j}$$x=\left(\prod _{i}u_{i}\right){\bmod {m}},\quad y=\prod _{j=0}^{h}p_{j}^{\gamma _{j}}$ ,

где ${\mathrm{\gamma <!--\; \gamma \; -->}}_j=\frac{1}{2}\underset{i}{\sum <!--\; \sum \; -->}{\mathrm{\alpha <!--\; \alpha \; -->}}_{ij}$$\gamma _{j}={\frac {1}{2}}\sum _{i}\alpha _{ij}$ . Тогда $x^2\equiv <!--\; \equiv \; -->y^2(\mathrm{mod}m)$$x^{2}\equiv y^{2}{\pmod {m}}$ .

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

АлгоритмПравить

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

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

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

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

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

$u_i^{2}modm=\underset{j=0}{\overset{h}{\prod <!--\; \prod \; -->}}{p}_j^{{\mathrm{\alpha <!--\; \alpha \; -->}}_{ij}}={\mathrm{\upsilon <!--\; \upsilon \; -->}}_i$$u_{i}^{2}{\bmod {m}}=\prod _{j=0}^{h}p_{j}^{\alpha _{ij}}=\upsilon _{i}$ ,

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

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

4. Положить $x\leftarrow <!--\; \leftarrow \; -->\underset{i\in <!--\; \in \; -->K}{\prod <!--\; \prod \; -->}{u}_{i}modm,y\leftarrow <!--\; \leftarrow \; -->\underset{j=1}{\overset{h}{\prod <!--\; \prod \; -->}}{p}_j^{\frac{1}{2}\underset{i\in <!--\; \in \; -->K}{\sum <!--\; \sum \; -->}{\mathrm{\alpha <!--\; \alpha \; -->}}_{ij}}modm$$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 <!--\; \equiv \; -->y^2(\mathrm{mod}m)$$x^{2}\equiv y^{2}{\pmod {m}}$ .

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

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

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

Некоторые улучшенияПравить

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

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

ОбоснованиеПравить

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

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

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

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

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

ПримерыПравить

Пример 1

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

1. Будем раскладывать число $\mathrm{\xi <!--\; \xi \; -->}=\sqrt{m}=\sqrt{1081}$$\xi ={\sqrt {m}}={\sqrt {1081}}$  в непрерывную дробь и записывать числа $A_n,B_n$$A_{n},B_{n}$  в таблицу для получения уравнений вида $u^2\equiv <!--\; \equiv \; -->\mathrm{\upsilon <!--\; \upsilon \; -->}(\mathrm{mod}m)$$u^{2}\equiv \upsilon {\pmod {m}}$ .

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

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

2. Теперь запишем сравнения $-<!--\; -\; -->B_n{B}_{n-<!--\; -\; -->1}\equiv <!--\; \equiv \; -->A_n^2(\mathrm{mod}m)$$-B_{n}B_{n-1}\equiv A_{n}^{2}{\pmod {m}}$  для $n=2,3,4,5,6$$n=2,3,4,5,6$ :

$-<!--\; -\; -->2^3\cdot <!--\; \cdot \; -->3\cdot <!--\; \cdot \; -->19\equiv <!--\; \equiv \; -->{25}^2(\mathrm{mod}1081),$$-2^{3}\cdot 3\cdot 19\equiv 25^{2}{\pmod {1081}},$ 

$-<!--\; -\; -->2^3\cdot <!--\; \cdot \; -->3\cdot <!--\; \cdot \; -->5\equiv <!--\; \equiv \; -->{31}^2(\mathrm{mod}1081),$$-2^{3}\cdot 3\cdot 5\equiv 31^{2}{\pmod {1081}},$ 

$-<!--\; -\; -->2^4\cdot <!--\; \cdot \; -->3\cdot <!--\; \cdot \; -->5\equiv <!--\; \equiv \; -->{29}^2(\mathrm{mod}1081),$$-2^{4}\cdot 3\cdot 5\equiv 29^{2}{\pmod {1081}},$ 

$-<!--\; -\; -->2^4\cdot <!--\; \cdot \; -->3^2\cdot <!--\; \cdot \; -->5\equiv <!--\; \equiv \; -->{19}^2(\mathrm{mod}1081),$$-2^{4}\cdot 3^{2}\cdot 5\equiv 19^{2}{\pmod {1081}},$ 

$-<!--\; -\; -->3^4\cdot <!--\; \cdot \; -->5\equiv <!--\; \equiv \; -->{26}^2(\mathrm{mod}1081).$$-3^{4}\cdot 5\equiv 26^{2}{\pmod {1081}}.$ 

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

$(-<!--\; -\; -->1{)}^2\cdot <!--\; \cdot \; -->2^4\cdot <!--\; \cdot \; -->3^2\cdot <!--\; \cdot \; -->5\cdot <!--\; \cdot \; -->3^4\cdot <!--\; \cdot \; -->5\equiv <!--\; \equiv \; -->{19}^2\cdot <!--\; \cdot \; -->{26}^2(\mathrm{mod}1081),$$(-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$$3^{2}$ :

$2^4\cdot <!--\; \cdot \; -->3^6\cdot <!--\; \cdot \; -->5^2\equiv <!--\; \equiv \; -->{19}^2\cdot <!--\; \cdot \; -->{26}^2(\mathrm{mod}1081)$$2^{4}\cdot 3^{6}\cdot 5^{2}\equiv 19^{2}\cdot 26^{2}{\pmod {1081}}$  или ${540}^2\equiv <!--\; \equiv \; -->{494}^2(\mathrm{mod}1081).$$540^{2}\equiv 494^{2}{\pmod {1081}}.$ 

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

Пример 2

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

1. Строим базу разложения из маленьких простых чисел, выбирая числа, по модулю которых $m$$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.$$\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\}$$B=\{-1,2,3,5,7,11,19\}$ , $h=6$$h=6$ .

2. Ищем числители $P_i$$P_{i}$  подходящих дробей к числу $\sqrt{m}$${\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 <!--\; \dots \; -->].$${\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}modm$$P_{i}^{2}{\bmod {m}}$  являются B-гладкими. Результаты вычислений записываем в таблицу:

k	i	Pi	P2i $(\mathrm{mod}m)$${\pmod {m}}$	ei
1	2	27691	$-<!--\; -\; -->4235=-<!--\; -\; -->1\cdot <!--\; \cdot \; -->5\cdot <!--\; \cdot \; -->7\cdot <!--\; \cdot \; -->{11}^2$$-4235=-1\cdot 5\cdot 7\cdot 11^{2}$	(1, 0, 0, 1, 1, 0, 0)
2	3	50767	$2688=2^7\cdot <!--\; \cdot \; -->3\cdot <!--\; \cdot \; -->7$$2688=2^{7}\cdot 3\cdot 7$	(0, 1, 1, 0, 1, 0, 0)
3	6	1389169	$-<!--\; -\; -->7920=-<!--\; -\; -->1\cdot <!--\; \cdot \; -->2^4\cdot <!--\; \cdot \; -->3^2\cdot <!--\; \cdot \; -->5\cdot <!--\; \cdot \; -->11$$-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 <!--\; \cdot \; -->7\cdot <!--\; \cdot \; -->11$$385=5\cdot 7\cdot 11$	(0, 0, 0, 1, 1, 1, 0)
5	16	2764443209657	$-<!--\; -\; -->3800=-<!--\; -\; -->1\cdot <!--\; \cdot \; -->2^3\cdot <!--\; \cdot \; -->5^2\cdot <!--\; \cdot \; -->19$$-3800=-1\cdot 2^{3}\cdot 5^{2}\cdot 19$	(1, 1, 0, 0, 0, 0, 1)
6	18	20276855015255	$-<!--\; -\; -->1331=-<!--\; -\; -->1\cdot <!--\; \cdot \; -->{11}^3$$-1331=-1\cdot 11^{3}$	(1, 0, 0, 0, 0, 1, 0)
7	19	127498600693396	$5415=3\cdot <!--\; \cdot \; -->5\cdot <!--\; \cdot \; -->{19}^2$$5415=3\cdot 5\cdot 19^{2}$	(0, 0, 1, 1, 0, 0, 0)
8	24	2390521616955537	$-<!--\; -\; -->112=-<!--\; -\; -->1\cdot <!--\; \cdot \; -->2^4\cdot <!--\; \cdot \; -->7$$-112=-1\cdot 2^{4}\cdot 7$	(1, 0, 0, 0, 1, 0, 0)

3. Поскольку $e_1\oplus <!--\; \oplus \; -->e_3\oplus <!--\; \oplus \; -->e_6\oplus <!--\; \oplus \; -->e_8=0$$e_{1}\oplus e_{3}\oplus e_{6}\oplus e_{8}=0$ , то получаем

4. $x=P_2\cdot <!--\; \cdot \; -->P_6\cdot <!--\; \cdot \; -->P_{18}\cdot <!--\; \cdot \; -->P_{24}\equiv <!--\; \equiv \; -->12487442(\mathrm{mod}m)$$x=P_{2}\cdot P_{6}\cdot P_{18}\cdot P_{24}\equiv 12487442{\pmod {m}}$ ,

$y=2^4\cdot <!--\; \cdot \; -->3^1\cdot <!--\; \cdot \; -->5^1\cdot <!--\; \cdot \; -->7^1\cdot <!--\; \cdot \; -->{11}^3\cdot <!--\; \cdot \; -->{19}^0=2236080$$y=2^{4}\cdot 3^{1}\cdot 5^{1}\cdot 7^{1}\cdot 11^{3}\cdot 19^{0}=2236080$ ,

$x^2\equiv <!--\; \equiv \; -->y^2\equiv <!--\; \equiv \; -->13201055(\mathrm{mod}m)$$x^{2}\equiv y^{2}\equiv 13201055{\pmod {m}}$ .

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

Поэтому, $21299881=3851\cdot <!--\; \cdot \; -->5531$$21299881=3851\cdot 5531$ .

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

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

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

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

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

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

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

$2⩽<!--\; ⩽\; -->p⩽<!--\; ⩽\; -->L^a,\left(\frac{m}{p}\right)=+1$$2\leqslant p\leqslant L^{a},\quad \left({\frac {m}{p}}\right)=+1$ ,

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

См. такжеПравить

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

ЛитератураПравить

• Lehmer D. H., Powers R. E. On factoring large numbers (англ.) // Bull., New Ser., Am. Math. Soc. / S. Friedlander — Providence, R.I.: American Mathematical Society, 1931. — Vol. 33, Iss. 1. — P. 35—36. — ISSN 0273-0979; 1088-9485 — doi:10.1090/S0002-9904-1931-05271-X
• Morrison M. A., Brillhart J. A Method of Factoring and the Factorization of F₇ (англ.) // Math. Comp. — AMS, 1975. — Vol. 29, Iss. 129. — P. 183—205. — ISSN 0025-5718; 1088-6842 — doi:10.2307/2005475
• Pomerance C. Analysis and comparison of some integer factoring algorithms (англ.) // Computational Methods in Number Theory: Part I / H. Lenstra, R. Tijdeman — Amsterdam: Mathematisch Centrum, 1982. — P. 89—139.
• Манин, Ю. И., Панчишкин, А. А. Глава 3.4. Метод непрерывных дробей (CFRAC) и вещественные квадратичные поля // Введение в теорию чисел, Теория чисел – 1. — Итоги науки и техн. Сер. Соврем. пробл. мат. Фундам. направления. — М.: ВИНИТИ, 1990. — Т. 49. — С. 77-80. — 341 с.
• Pomerance C. A Tale of Two Sieves (англ.) // Notices Amer. Math. Soc. / F. Morgan — AMS, 1996. — Vol. 43. — P. 1473—1485. — ISSN 0002-9920; 1088-9477
• Введение в криптографию / Ященко, В. В.. — Москва: МЦНМО, 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