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

 В теории чисел факторизация методом непрерывных дробей(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
,
 где x=a+b2,y=ab2.
 Отсюда видно, что x2m=y2. Значит, если последовательноперебирать квадраты целых чисел x, начиная с ближайшего сверху к mквадрата, то на некоторой итерации разность x2m окажется равнаквадрату некоторого числа y. Найденная пара чисел (x,y) позволитнайти пару множителей (a,b) числа m:a=x+y2,b=xy2.
 Таким образом, метод Ферма сводит задачу факторизации числа к поискуцелых чисел, разность которых равна исходному числу m. Метод Фермабыстро находит множители числа m в том случае, когда его делителиблизки к m, т.е. для максимально негладких чисел. Если же числоm является гладким, то метод Ферма может работать даже медленнейметода пробных делений.
 В 1926 году в монографии представил свой метод факторизации целых чисел,который представлял собой ``усиление'' метода Ферма.
 Крайчик предложил вместо пар чисел (x,y), удовлетворяющих соотношениюx2y2=m, искать пары (x,y), удовлетворяющие сравнениюx2y20(modm), т.е. x2y2(modm). Если, приэтом, x±y(modm), то мы получим лишь тривиальное решение.Однако, если x±y(modm), то из указанного сравненияполучается x2y2=(xy)(x+y)=km, где kZ.Отсюда тоже следует разложение: m делится на (xy)(x+y), но неделится ни на xy, ни на x+y, следовательно gcd(xy,m) -нетривиальный делитель m. (см. \#обоснование1)
 После нововведения Крайчика алгоритм нахождения делителей числа mзначительно изменялся: теперь по-прежнему нужно вычислять x2m дляразных x, однако теперь не требуется ``ждать'' другой квадрат, а нужнопытаться его построить, перемножая полученные числа m.
 Действительно, рассмотрим последовательность чисел видаυ(u)=u2m (очевидно, υu2(modm)).Тогда, если υ(u1)υ(u2)υ(uk)=y2,т.е. (u21m)(u22m)(u2km)=y2, то отсюдаследует, что x2=u21u22u2ky2(modm). Длятого, чтобы определить, какие именно соотношения нужно перемножить,необходимо раскладывать числа υ на множители и перемножатьсоотношения так, чтобы в произведенияхυ1υ2υk присутствовали простыемножители в четных степенях, позволяющие получить сравнениеx2y2(modm).
 Метод Крайчика сводит задачу разложения числа m на множители кпостроению некоторого количества сравнений u2υ(modm)и разложению на множители чисел υ. Однако Крайчик не предъявилконкретный алгоритм поиска пар чисел u,υ и алгоритмическийспособ составления из найденных соотношений сравнения видаx2y2(modm).
 В 1931 году в работе Лемер и Пауэрс предложили два варианта генерацииуказанных сравнений. Оба варианта основывались на соотношениях,возникающих при разложении квадратичных иррациональностей в непрерывныедроби, и обладали тем свойством, что величины υ не превосходили2m. Последнее неравенство гарантирует, что числа υбудут маленькими, что облегчит разложение этих чисел на простыемножители.(см. \#обоснование2)
 При этом, оба варианта оказываются эквивалентными: если один варианталгоритма найдет решение, то и второй вариант также найдет решение.
 Однако, у обоих вариантов алгоритма был недостаток — разложениеквадратичной иррациональности в непрерывную дробь периодично (теоремаЛагранжа). Поэтому количество соотношений, которые можно получить спомощью данного метода, ограниченно, и их может оказаться недостаточнодля набора соотношений и построения сравнения x2y2(modm).При этом, как показывают практические эксперименты, при большихзначениях m длина периода разложения в непрерывную дробь оказываетсядостаточно большой(порядка m) для составления требуемого числасравнений. В результате при больших m оба варианта алгоритма всегданаходят разложение числа m на множители.

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

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

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

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

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

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

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

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

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

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

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


 В начале 1970-х годов в статье Майкл Моррисон и Джон Бриллхартпредложили свой алгоритм, являющийся модификацией второго вариантаалгоритма Лемера и Пауэрса. В настоящее время под методом непрерывныхдробей понимают именно алгоритм Моррисона и Бриллхарта.
 Основное отличие реализованного Моррисоном и Бриллхартом алгоритма отпервоначального варианта заключалось в введении процедурыалгоритмического построения сравнения x2y2(modm) позаданному множеству сравнений вида u2υ(modm). Дляреализации этой процедуры использовалось понятие «факторной базы».
 Будем искать x как произведение таких чисел ui, что наименьший поабсолютной величине вычет числа u2i по модулю m являетсяпроизведением простых чисел. Тогда из тех же простых чисел можнопостроить и y.
Базой факторизации (или факторной базой) натуральногочисла m называется множество B={p0,p1,,ph}различных простых чисел pi, за возможным исключением p0, котороеможет быть равным -1. При этом число b, для которого b2modmявляется произведением степеней чисел из множества B, называетсяB-гладким числом. Пусть теперь ui — B-гладкие числа,υi=u2imodm=hj=0pαijj —разложения их наименьшие по абсолютной величине вычетов по модулю m.Положим
ei=(ei0,ei1,,eih)Fh2
,где eijαijmod2, Fh2 — векторноепространство над полем GF(2), которое состоит из наборов нулей и единицразмерности h.
 Подберем числа ui так, чтобы сумма векторов ei была равнанулю. Определим
x=(iui)modm,y=hj=0pγjj
,
 где γ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] арифметическихопераций.