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

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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Действительно, рассмотрим последовательность чисел вида $\upsilon (u)=u^2-m$ (очевидно, $\upsilon \equiv u^2(\mathrm{mod}m)$). Тогда, если $\upsilon (u_1)\upsilon (u_2)\dots \upsilon (u_k)=y^2$, т.е. $(u_1^2-m)(u_2^2-m)\dots (u_k^2-m)=y^2$, то отсюда следует, что $x^2=u_1^2{u}_2^2\dots u_k^2\equiv y^2(\mathrm{mod}m)$Шаблон:Sfn. Для того, чтобы определить, какие именно соотношения нужно перемножить, необходимо раскладывать числа $\upsilon$ на множители и перемножать соотношения так, чтобы в произведениях ${\upsilon }_1{\upsilon }_2\dots {\upsilon }_k$ присутствовали простые множители в четных степенях, позволяющие получить сравнение $x^2\equiv y^2(\mathrm{mod}m)$Шаблон:Sfn.

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

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

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

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

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

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

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

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

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

Для коэффициентов $A_n,B_n$ выполняется равенствоШаблон:Sfn:

$A_n^2+B_n{B}_{n-1}=m.$

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

$-B_n{B}_{n-1}\equiv A_n^2(\mathrm{mod}m),n=0,1,\dots .(1)$

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

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

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

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

$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_0=b_0,Q_0=P_{-1}=1,Q_{-1}=0$

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

$P_{n-1}^2-m{Q}_{n-1}=(-1{)}^n{B}_n$ ,

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

$P_{n-1}^2\equiv (-1{)}^n{B}_n(\mathrm{mod}m),n=1,2,\dots .(2)$

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

Алгоритм

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

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

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

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

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

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

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

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

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

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

${𝐞}_i=(e_{i0},e_{i1},\dots ,e_{ih})\in {𝔽}_2^h$,

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

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

$x=\left(\prod _i{u}_i\right)modm,y=\prod _{j=0}^h{p}_j^{{\gamma }_j}$,

где ${\gamma }_j=\frac{1}{2}\sum _i{\alpha }_{ij}$. Тогда $x^2\equiv y^2(\mathrm{mod}m)$.

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

Алгоритм

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

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

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

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

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

$u_i^{2}modm=\prod _{j=0}^h{p}_j^{{\alpha }_{ij}}={\upsilon }_i$,

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

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

4. Положить $x\leftarrow \prod _{i\in K}{u}_{i}modm,y\leftarrow \prod _{j=1}^h{p}_j^{\frac{1}{2}\sum _{i\in K}{\alpha }_{ij}}modm$. Тогда $x^2\equiv y^2(\mathrm{mod}m)$.

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

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

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

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

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

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

Обоснование

Следующая лемма показывает, что если выполнено сравнение $x^2\equiv y^2(\mathrm{mod}m)$ и $x\equiv ̸y(\mathrm{mod}m)$, то числа $x-y$ и $m$ имеют общие делители.Шаблон:Якорь

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

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

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

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

Примеры

Пример 1Шаблон:SfnШаблон:Якорь

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

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

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

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

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

$-2^3\cdot 3\cdot 19\equiv 25^2(\mathrm{mod}1081),$

$-2^3\cdot 3\cdot 5\equiv 31^2(\mathrm{mod}1081),$

$-2^4\cdot 3\cdot 5\equiv 29^2(\mathrm{mod}1081),$

$-2^4\cdot 3^2\cdot 5\equiv 19^2(\mathrm{mod}1081),$

$-3^4\cdot 5\equiv 26^2(\mathrm{mod}1081).$

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

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

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

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

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

Пример 2Шаблон:Sfn

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

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

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

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

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

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

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

k	i	Pi	PШаблон:Supi $(\mathrm{mod}m)$	ei
1	2	27691	$-4235=-1\cdot 5\cdot 7\cdot 11^2$	(1, 0, 0, 1, 1, 0, 0)
2	3	50767	$2688=2^7\cdot 3\cdot 7$	(0, 1, 1, 0, 1, 0, 0)
3	6	1389169	$-7920=-1\cdot 2^4\cdot 3^2\cdot 5\cdot 11$	(1, 0, 0, 1, 0, 1, 0)
4	13	12814433311	$385=5\cdot 7\cdot 11$	(0, 0, 0, 1, 1, 1, 0)
5	16	2764443209657	$-3800=-1\cdot 2^3\cdot 5^2\cdot 19$	(1, 1, 0, 0, 0, 0, 1)
6	18	20276855015255	$-1331=-1\cdot 11^3$	(1, 0, 0, 0, 0, 1, 0)
7	19	127498600693396	$5415=3\cdot 5\cdot 19^2$	(0, 0, 1, 1, 0, 0, 0)
8	24	2390521616955537	$-112=-1\cdot 2^4\cdot 7$	(1, 0, 0, 0, 1, 0, 0)

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

4. $x=P_2\cdot P_6\cdot P_{18}\cdot P_{24}\equiv 12487442(\mathrm{mod}m)$,

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

$x^2\equiv y^2\equiv 13201055(\mathrm{mod}m)$.

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Литература

• Шаблон:Source
• Шаблон:Source
• Шаблон:Source
• Шаблон:Книга
• Шаблон:Source
• Шаблон:Книга
• Шаблон:Source
• Шаблон:Source
• Шаблон:Source
• Шаблон:Source
• Шаблон:Source