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

 В теории чисел факторизация методом непрерывных дробей (CFRAC) — это алгоритм разложения целых чисел на простые множители. Это алгоритм общего вида, пригодный для факторизации произвольного целого m.
 Метод непрерывных дробей разработан на основе алгоритма Крайчика и использует непрерывную дробь, сходящуюся к kmkm для некоторого целого положительного числа k. На основе метода непрерывных дробей был построен алгоритм Диксона, по схеме которого затем был разработан метод квадратичного решета.
 Алгоритм имеет сложность O(e2logmloglogm)=Lm[1/2,2]O(e2logmloglogm)=Lm[1/2,2], в O и L нотациях.

История


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

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

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


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


 В 1643 году Пьер Ферма предложил алгоритм разложения на множители нечетного целого числа mm. Кратко этот алгоритм можно описать так: пусть m=abm=ab. Тогда, можно записать
ab=(a+b2)2(ab2)2=x2y2=m
ab=(a+b2)2(ab2)2=x2y2=m
,
 где x=a+b2,y=ab2x=a+b2,y=ab2.
 Отсюда видно, что x2m=y2x2m=y2. Значит, если последовательно перебирать квадраты целых чисел xx, начиная с ближайшего сверху к mm квадрата, то на некоторой итерации разность x2mx2m окажется равна квадрату некоторого числа yy. Найденная пара чисел (x,y)(x,y) позволит найти пару множителей (a,b)(a,b) числа mm: a=x+y2,b=xy2a=x+y2,b=xy2.
 Таким образом, метод Ферма сводит задачу факторизации числа к поиску целых чисел, разность которых равна исходному числу mm. Метод Ферма быстро находит множители числа mm в том случае, когда его делители близки к mm, т.е. для максимально негладких чисел. Если же число mm является гладким, то метод Ферма может работать даже медленней метода пробных делений.
 В 1926 году в монографии представил свой метод факторизации целых чисел, который представлял собой ``усиление'' метода Ферма.
 Крайчик предложил вместо пар чисел (x,y)(x,y), удовлетворяющих соотношению x2y2=mx2y2=m, искать пары (x,y)(x,y), удовлетворяющие сравнению x2y20(modm)x2y20(modm), т.е. x2y2(modm)x2y2(modm). Если, при этом, x±y(modm)x±y(modm), то мы получим лишь тривиальное решение. Однако, если x±y(modm)x≢±y(modm), то из указанного сравнения получается x2y2=(xy)(x+y)=kmx2y2=(xy)(x+y)=km, где kZkZ. Отсюда тоже следует разложение: mm делится на (xy)(x+y)(xy)(x+y), но не делится ни на xyxy, ни на x+yx+y, следовательно gcd(xy,m)gcd(xy,m) - нетривиальный делитель mm. (см. \#обоснование1)
 После нововведения Крайчика алгоритм нахождения делителей числа mm значительно изменялся: теперь по-прежнему нужно вычислять x2mx2m для разных xx, однако теперь не требуется ``ждать'' другой квадрат, а нужно пытаться его построить, перемножая полученные числа mm.
 Действительно, рассмотрим последовательность чисел вида υ(u)=u2mυ(u)=u2m (очевидно, υu2(modm)υu2(modm)). Тогда, если υ(u1)υ(u2)υ(uk)=y2υ(u1)υ(u2)υ(uk)=y2, т.е. (u21m)(u22m)(u2km)=y2(u21m)(u22m)(u2km)=y2, то отсюда следует, что x2=u21u22u2ky2(modm)x2=u21u22u2ky2(modm). Для того, чтобы определить, какие именно соотношения нужно перемножить, необходимо раскладывать числа υυ на множители и перемножать соотношения так, чтобы в произведениях υ1υ2υkυ1υ2υk присутствовали простые множители в четных степенях, позволяющие получить сравнение x2y2(modm)x2y2(modm).
 Метод Крайчика сводит задачу разложения числа mm на множители к построению некоторого количества сравнений u2υ(modm)u2υ(modm) и разложению на множители чисел υυ. Однако Крайчик не предъявил конкретный алгоритм поиска пар чисел u,υu,υ и алгоритмический способ составления из найденных соотношений сравнения вида x2y2(modm)x2y2(modm).
 В 1931 году в работе Лемер и Пауэрс предложили два варианта генерации указанных сравнений. Оба варианта основывались на соотношениях, возникающих при разложении квадратичных иррациональностей в непрерывные дроби, и обладали тем свойством, что величины υυ не превосходили 2m2m. Последнее неравенство гарантирует, что числа υυ будут маленькими, что облегчит разложение этих чисел на простые множители.(см. \#обоснование2)
 При этом, оба варианта оказываются эквивалентными: если один вариант алгоритма найдет решение, то и второй вариант также найдет решение.
 Однако, у обоих вариантов алгоритма был недостаток — разложение квадратичной иррациональности в непрерывную дробь периодично (теорема Лагранжа). Поэтому количество соотношений, которые можно получить с помощью данного метода, ограниченно, и их может оказаться недостаточно для набора соотношений и построения сравнения x2y2(modm)x2y2(modm). При этом, как показывают практические эксперименты, при больших значениях mm длина периода разложения в непрерывную дробь оказывается достаточно большой(порядка mm) для составления требуемого числа сравнений. В результате при больших mm оба варианта алгоритма всегда находят разложение числа mm на множители.

agraphПервый вариант
 Напомним, что каждому действительному числу ξξ может быть поставлена в соответствие последовательность целых чисел [b0,b1,b2,...][b0,b1,b2,...], называемая его непрерывной дробью. Это сопоставление строится следующим образом
x0=ξ,bi=[xi],xi+1=1xibi,i=0,1,2,.
x0=ξ,bi=[xi],xi+1=1xibi,i=0,1,2,.

 При этом ξ=b0+1b1+1b2+1+1xn=[b0,b1,b2,,bn1,xn].ξ=b0+1b1+1b2+1+1xn=[b0,b1,b2,,bn1,xn].
 Если раскладывать в непрерывную дробь число ξ=mξ=m, то возникающие в процессе разложения числа xnxn имеют вид xn=m+AnBnxn=m+AnBn с целыми An,BnAn,Bn, причем выполняется An<mAn<m, 0<Bn<2m0<Bn<2m.
 Для коэффициентов An,BnAn,Bn выполняется равенство:
A2n+BnBn1=m.
A2n+BnBn1=m.

 Отсюда следует
BnBn1A2n(modm),n=0,1,(1).
BnBn1A2n(modm),n=0,1,(1).

 Полученное равенство имеет вид u2υ(modm)u2υ(modm), предложенный Крайчиком, и может быть применено для факторизации числа mm.
 Вычисляя последовательно частные A0,B0,A1,B1,A0,B0,A1,B1,, будем получать выражения вида (1)(1) для различных nn. Раскладывая величины BnBn на простые множители и комбинируя полученные равенства, можно получить сравнения вида x2y2(modm)x2y2(modm) (см. \#пример1).

agraphВторой вариант
 С каждой непрерывной дробью свяжем последовательность рациональных чисел, состоящую из подходящих дробей PnQn=[b0,b1,,bn1,bn],n>0PnQn=[b0,b1,,bn1,bn],n>0, вычисляемых по формулам:
Pn+1=bn+1Pn+Pn1,Qn+1=bn+1Qn+Qn1,n0,
Pn+1=bn+1Pn+Pn1,Qn+1=bn+1Qn+Qn1,n0,

P0=b0,Q0=P1=1,Q1=0
P0=b0,Q0=P1=1,Q1=0

 и стремящихся к разлагаемому числу. Если в непрерывную дробь разлагается число ξ=mξ=m, то справедливо соотношение:
P2n1mQn1=(1)nBn
P2n1mQn1=(1)nBn
,
 из которого следует
P2n1(1)nBn(modm),n=1,2,(2)
P2n1(1)nBn(modm),n=1,2,(2)
.
 Полученное равенство имеет вид u2υ(modm)u2υ(modm), и может быть использовано для факторизации числа mm так же, как и в первом варианте.

agraphАлгоритм
 Таким образом, исправленный Лемером и Пауэрсом метод Крайчика имеет следующий вид.
Вход. Составное число mm.
Выход. Нетривиальный делитель pp числа mm.

  1. Разложить mm в непрерывную дробь.
  2. Используя равенства (1)(1) или (2)(2), получить множество сравнений вида u2υ(modm)u2υ(modm) и разложить числа υυ на простые множители.
  3. Выбрать те равенства u2υ(modm)u2υ(modm), перемножение которых даст произведение четных степеней простых чисел, полученных в результате разложения чисел υυ. Тем самым, мы получим соотношение вида x2y2(modm)x2y2(modm).
  4. Если x±y(modm)x±y(modm), то вернуться на шаг 3. Если имеющегося числа соотношений недостаточно для генерации равенства x2y2(modm)x2y2(modm), то необходимо продолжить разложение числа mm в непрерывную дробь и, затем, вернуться на шаг 2.
  5. С помощью алгоритма Евклида определить p=gcd(xy,m)p=gcd(xy,m).

 Лемер и Пауэрс в своей работе указали, как можно генерировать соотношения вида u2υ(modm)u2υ(modm), однако они, также как и Крайчик, не дали алгоритмического способа составления из найденных соотношений сравнения x2y2(modm)x2y2(modm). Эту проблему решил метод Моррисона и Бриллхарта.

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


 В начале 1970-х годов в статье Майкл Моррисон и Джон Бриллхарт предложили свой алгоритм, являющийся модификацией второго варианта алгоритма Лемера и Пауэрса. В настоящее время под методом непрерывных дробей понимают именно алгоритм Моррисона и Бриллхарта.
 Основное отличие реализованного Моррисоном и Бриллхартом алгоритма от первоначального варианта заключалось в введении процедуры алгоритмического построения сравнения x2y2(modm)x2y2(modm) по заданному множеству сравнений вида u2υ(modm)u2υ(modm). Для реализации этой процедуры использовалось понятие «факторной базы».
 Будем искать xx как произведение таких чисел uiui, что наименьший по абсолютной величине вычет числа u2iu2i по модулю mm является произведением простых чисел. Тогда из тех же простых чисел можно построить и yy.
Базой факторизации (или факторной базой) натурального числа mm называется множество B={p0,p1,,ph}B={p0,p1,,ph} различных простых чисел pipi, за возможным исключением p0p0, которое может быть равным -1. При этом число bb, для которого b2modmb2modm является произведением степеней чисел из множества BB, называется B-гладким числом. Пусть теперь uiui — B-гладкие числа, υi=u2imodm=hj=0pαijjυi=u2imodm=hj=0pαijj — разложения их наименьшие по абсолютной величине вычетов по модулю mm. Положим
ei=(ei0,ei1,,eih)Fh2
ei=(ei0,ei1,,eih)Fh2
, где eijαijmod2eijαijmod2, Fh2Fh2 — векторное пространство над полем GF(2), которое состоит из наборов нулей и единиц размерности hh.
 Подберем числа uiui так, чтобы сумма векторов eiei была равна нулю. Определим
x=(iui)modm,y=hj=0pγjj
x=(iui)modm,y=j=0hpγjj
,
 где γj=12iαijγj=12iαij. Тогда x2y2(modm).
 Осталось добавить, что факторная база в алгоритме Моррисона и Бриллхарта состоит из тех простых чисел pi, по модулю которых m является квадратичным вычетом.

agraphАлгоритм
 Алгоритм Моррисона и Бриллхарта выглядит следующим образом.
Вход. Составное число m.
Выход. Нетривиальный делитель p числа m.
 1. Построить базу разложения B={p0,p1,,ph}, где p0=1 и p1,,ph — попарно различные простые числа, по модулю которых m является квадратичным вычетом.
 2. Берутся целые числа ui, являющиеся числителями подходящих дробей к обыкновенной непрерывной дроби, выражающей число m. Из этих числителей выбираются h+2 чисел, для которых абсолютно наименьшие вычеты u2i по модулю m являются B-гладкими:
u2imodm=hj=0pαijj=υi
,
 где αij0. Также каждому числу ui сопоставляется вектор показателей (αi0,αi1,,αih).
 3. Найти (например, методом Гаусса) такое непустое множество K{1,2,,h+1}, что iKei=0, где — операция исключающее ИЛИ, ei=(ei1,ei2,,eih),eijαij(mod2), 0jh.
 4. Положить xiKuimodm,yhj=1p12iKαijjmodm. Тогда x2y2(modm).
 5. Если xy(modm), то положить pgcd(xy,m) и выдать результат: p.

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

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


 Пусть m=pq. Выше в непрерывную дробь раскладывалось число m. Такой вариант эффективен, когда p и q близки друг к другу. Однако, чем больше разность между числами p и q, тем более трудоемким становится алгоритм. В этом случае вместо m можно раскладывать в непрерывную дробь число km , где маленький множитель k подбирается так, чтобы в базу множителей вошли все малые простые.
 Кроме того, так как метод непрерывных дробей построен по схеме алгоритма Диксона, то для него применимы дополнительные стратегии алгоритма Диксона.

Обоснование


 Следующая лемма показывает, что если выполнено сравнение x2y2(modm) и xy(modm), то числа xy и m имеют общие делители.
Лемма(о факторизации). Пусть m — нечётное составное число и x,y — вычеты по модулю m такие, что x±y(modm) и x2y2(modm). Тогда выполняется неравенство 1<gcd(xy,m)<m.
 Следующие два утверждения — ключевые для алгоритма факторизации методом непрерывных дробей. Они показывают, что можно найти последовательность чисел ui, квадраты которых имеют малые вычеты по модулю m.
Теорема. Если PnQn, где n=1,2,, — подходящие дроби к числу α>1, которое задано обыкновенной непрерывной дробью, то для всех n справедлива оценка |P2nα2Q2n|<2α.
Следствие. Пусть положительное число m не является полным квадратом и PnQn, где n=1,2,, — подходящие дроби к числу m. Тогда для абсолютно наименьшего вычета P2nmodm (т.е. для вычета, расположенного между m2 и m2) справедливо неравенство |P2nmodm|<2m, причем P2nmodm=P2nmQ2n.

Примеры




Пример 1 
  Разложим на множители первым алгоримом Лемера и Пауэрса число m=1081.
 1. Будем раскладывать число ξ=m=1081 в непрерывную дробь и записывать числа An,Bn в таблицу для получения уравнений вида u2υ(modm).
kiPiPi (modm)ei
12276914235=157112(1, 0, 0, 1, 1, 0, 0)
23507672688=2737(0, 1, 1, 0, 1, 0, 0)
3613891697920=12432511(1, 0, 0, 1, 0, 1, 0)
41312814433311385=5711(0, 0, 0, 1, 1, 1, 0)
51627644432096573800=1235219(1, 1, 0, 0, 0, 0, 1)
618202768550152551331=1113(1, 0, 0, 0, 0, 1, 0)
7191274986006933965415=35192(0, 0, 1, 1, 0, 0, 0)
8242390521616955537112=1247(1, 0, 0, 0, 1, 0, 0)

 3. Поскольку e1e3e6e8=0, то получаем
 4. x=P2P6P18P2412487442(modm),
y=24315171113190=2236080
,
x2y213201055(modm)
.
 5. Условие x±y(modm) выполнено, поэтому вычисляем p=gcd(xy,m)=gcd(10251362,21299881)=3851.
 Поэтому, 21299881=38515531.

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


 С появлением криптосистемы RSA в конце 1970-х годов стала особенно важна вычислительная сложность алгоритмов факторизации.
 Эвристический анализ времени выполнения алгоритма Морриса и Брилхарта был проведен в 1975 году, хотя не был опубликован.
 Более точная оценка(которая при этом все равно оставалась эвристической) была проведена в работе. Приведем результаты оценки сложности в соответствии с этой работой.
 При получении оценок в этой работе делаются некоторые эвристические допущения. Например, предполагают, что если помощью алгоритма построено 1+[log2m] пар (x,y) таких, что x2y2(modm), то хотя бы для одной из них выполнены неравенства
1<gcd(x±y,m)
.
Утверждение. Если a=12, L=L(m)=exp((logmloglogm)1/2) и факторная база состоит из p=1 и всех простых чисел p таких, что
2pLa,(mp)=+1
,
 то при вычислении Lb подходящих дробей (где b=a+14a) можно ожидать, что алгоритм разложит m на два множителя с эвристической оценкой сложности Lm[12;2] арифметических операций.