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

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

Метод непрерывных дробей разработан на основе алгоритма Крайчика и использует непрерывную дробь, сходящуюся к для некоторого целого положительного числа . На основе метода непрерывных дробей был построен алгоритм Диксона, по схеме которого, затем, был разработан метод квадратичного решета[1].

Алгоритм имеет сложность , в O и L нотациях[2].

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

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

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

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

 

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

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

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

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

 ,

где  .

Отсюда видно, что  . Значит, если последовательно перебирать квадраты целых чисел  , начиная с ближайшего сверху к   квадрата, то на некоторой итерации разность   окажется равна квадрату некоторого числа  . Найденная пара чисел   позволит найти пару множителей   числа  :  .

Таким образом, метод Ферма сводит задачу факторизации числа к поиску целых чисел, разность которых равна исходному числу  . Метод Ферма быстро находит множители числа   в том случае, когда его делители близки к  , т.е. для максимально негладких чисел. Если же число   является гладким, то метод Ферма может работать даже медленней метода пробных делений[2].

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

Крайчик предложил вместо пар чисел  , удовлетворяющих соотношению  , искать пары  , удовлетворяющие сравнению  , т.е.  . Если, при этом,  , то мы получим лишь тривиальное решение. Однако, если  , то из указанного сравнения получается  , где  . Отсюда тоже следует разложение:   делится на  , но не делится ни на  , ни на  , следовательно   — нетривиальный делитель  [2] (см. #обоснование1).

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

Действительно, рассмотрим последовательность чисел вида   (очевидно,  ). Тогда, если  , т.е.  , то отсюда следует, что  [2]. Для того, чтобы определить, какие именно соотношения нужно перемножить, необходимо раскладывать числа   на множители и перемножать соотношения так, чтобы в произведениях   присутствовали простые множители в четных степенях, позволяющие получить сравнение  [8].

Метод Крайчика сводит задачу разложения числа   на множители к построению некоторого количества сравнений   и разложению на множители чисел  . Однако Крайчик не предъявил конкретный алгоритм поиска пар чисел   и алгоритмический способ составления из найденных соотношений сравнения вида  [8].

В 1931 году в работе[3] Лемер и Пауэрс предложили два варианта генерации указанных сравнений. Оба варианта основывались на соотношениях, возникающих при разложении квадратичных иррациональностей в непрерывные дроби, и обладали тем свойством, что величины   не превосходили   [9]. Последнее неравенство гарантирует, что числа   будут маленькими, что облегчит разложение этих чисел на простые множители[2](см. #обоснование2).

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

Однако, у обоих вариантов алгоритма был недостаток — разложение квадратичной иррациональности в непрерывную дробь периодично (теорема Лагранжа). Поэтому количество соотношений, которые можно получить с помощью данного метода, ограниченно, и их может оказаться недостаточно для набора соотношений и построения сравнения  . При этом, как показывают практические эксперименты, при больших значениях   длина периода разложения в непрерывную дробь оказывается достаточно большой (порядка   [10]) для составления требуемого числа сравнений. В результате при больших   оба варианта алгоритма всегда находят разложение числа   на множители[11].

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

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

 

При этом  

Если раскладывать в непрерывную дробь число  , то возникающие в процессе разложения числа   имеют вид   с целыми  , причем выполняется  ,  [12].

Для коэффициентов   выполняется равенство[3]:

 

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

 

Полученное равенство имеет вид  , предложенный Крайчиком, и может быть применено для факторизации числа  .

Вычисляя последовательно частные  , будем получать выражения вида   для различных  . Раскладывая величины   на простые множители и комбинируя полученные равенства, можно получить сравнения вида   (см. #пример1).

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

С каждой непрерывной дробью свяжем последовательность рациональных чисел, состоящую из подходящих дробей  , вычисляемых по формулам[3]:

 
 

и стремящихся к разлагаемому числу. Если в непрерывную дробь разлагается число  , то справедливо соотношение[12]:

  ,

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

 

Полученное равенство имеет вид   и может быть использовано для факторизации числа   так же, как и в первом варианте.

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

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

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

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

  1. Разложить   в непрерывную дробь.
  2. Используя равенства   или  , получить множество сравнений вида   и разложить числа   на простые множители.
  3. Выбрать те равенства  , перемножение которых даст произведение четных степеней простых чисел, полученных в результате разложения чисел  . Тем самым, мы получим соотношение вида  .
  4. Если  , то вернуться на шаг 3. Если имеющегося числа соотношений недостаточно для генерации равенства  , то необходимо продолжить разложение числа   в непрерывную дробь и, затем, вернуться на шаг 2.
  5. С помощью алгоритма Евклида определить  .

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

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

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

Основное отличие реализованного Моррисоном и Бриллхартом алгоритма от первоначального варианта заключалось в введении процедуры алгоритмического построения сравнения   по заданному множеству сравнений вида  . Для реализации этой процедуры использовалось понятие «факторной базы»[11].

Будем искать   как произведение таких чисел  , что наименьший по абсолютной величине вычет числа   по модулю   является произведением простых чисел[14]. Тогда из тех же простых чисел можно построить и  .

Базой факторизации (или факторной базой) натурального числа   называется множество   различных простых чисел  , за возможным исключением  , которое может быть равным  . При этом число  , для которого   является произведением степеней чисел из множества  , называется B-гладким числом. Пусть теперь   — B-гладкие числа,   — разложения их наименьшие по абсолютной величине вычетов по модулю  . Положим

 ,

где  ,  векторное пространство над полем GF(2), которое состоит из наборов нулей и единиц размерности  .

Подберем числа   так, чтобы сумма векторов   была равна нулю. Определим

 ,

где  . Тогда  .

Осталось добавить, что факторная база в алгоритме Моррисона и Бриллхарта состоит из тех простых чисел  , по модулю которых   является квадратичным вычетом[15].

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

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

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

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

1. Построить базу разложения  , где   и   — попарно различные простые числа, по модулю которых   является квадратичным вычетом.

2. Берутся целые числа  , являющиеся числителями подходящих дробей к обыкновенной непрерывной дроби, выражающей число  . Из этих числителей выбираются   чисел, для которых абсолютно наименьшие вычеты   по модулю   являются B-гладкими:

 ,

где  . Также каждому числу   сопоставляется вектор показателей  .

3. Найти (например, методом Гаусса) такое непустое множество  , что  , где   — операция исключающее ИЛИ,  ,  .

4. Положить  . Тогда  .

5. Если  , то положить   и выдать результат:  .

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

Из полученного алгоритма впоследствии был разработан алгоритм Диксона, из которого был удален аппарат цепных дробей[17]. После создания алгоритма Диксона, метод непрерывных дробей, по сути, представлял собой алгоритм Диксона, в котором был уточнен выбор абсолютно наименьшего вычета  [18].

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

Пусть  . Выше в непрерывную дробь раскладывалось число  . Такой вариант эффективен, когда   и   близки друг к другу. Однако, чем больше разность между числами   и  , тем более трудоемким становится алгоритм. В этом случае вместо   можно раскладывать в непрерывную дробь число   , где маленький множитель   подбирается так, чтобы в базу множителей вошли все малые простые[19].

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

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

Следующая лемма показывает, что если выполнено сравнение   и  , то числа   и   имеют общие делители.

Лемма(о факторизации)[20]. Пусть   — нечётное составное число и   — вычеты по модулю   такие, что   и  . Тогда выполняется неравенство  .

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

Теорема[21]. Если  , где  , — подходящие дроби к числу  , которое задано обыкновенной непрерывной дробью, то для всех   справедлива оценка  .

Следствие[21]. Пусть положительное число   не является полным квадратом и  , где  , — подходящие дроби к числу  . Тогда для абсолютно наименьшего вычета   (т.е. для вычета, расположенного между   и  ) справедливо неравенство  , причем  .

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

Пример 1[22]

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

1. Будем раскладывать число   в непрерывную дробь и записывать числа   в таблицу для получения уравнений вида  .

Таблица: факторизация числа 1081
i xi Ai Bi
1   32 57
2   25 8
3   31 15
4   29 16
5   19 45
6   26 9

2. Теперь запишем сравнения   для  :

 
 
 
 
 

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

 

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

  или  

4. Получили сравнение вида  , используя которое можно найти делитель числа 1081. Действительно,  . Тогда, второй делитель числа 1081 равен 47.

Пример 2[23]

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

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

 

Отсюда, факторная база будет равна  ,  .

2. Ищем числители   подходящих дробей к числу  :

 

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

k i Pi P2i   ei
1 2 27691   (1, 0, 0, 1, 1, 0, 0)
2 3 50767   (0, 1, 1, 0, 1, 0, 0)
3 6 1389169   (1, 0, 0, 1, 0, 1, 0)
4 13 12814433311   (0, 0, 0, 1, 1, 1, 0)
5 16 2764443209657   (1, 1, 0, 0, 0, 0, 1)
6 18 20276855015255   (1, 0, 0, 0, 0, 1, 0)
7 19 127498600693396   (0, 0, 1, 1, 0, 0, 0)
8 24 2390521616955537   (1, 0, 0, 0, 1, 0, 0)

3. Поскольку  , то получаем

4.  ,

 ,
 .

5. Условие   выполнено, поэтому вычисляем  .

Поэтому,  .

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

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

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

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

При получении оценок в этой работе делаются некоторые эвристические допущения. Например, предполагают, что если помощью алгоритма построено   пар   таких, что  , то хотя бы для одной из них выполнены неравенства

 .

Утверждение[26]. Если  ,   и факторная база состоит из   и всех простых чисел   таких, что:

 ,

то при вычислении   подходящих дробей, где  , можно ожидать, что алгоритм разложит   на два множителя с эвристической оценкой сложности   арифметических операций.

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

Примечания править

  1. Кнут, 2013, pp. 439,441.
  2. 1 2 3 4 5 6 7 8 Pomerance, 1996.
  3. 1 2 3 4 5 Lehmer, Powers, 1931.
  4. 1 2 Кнут, 2013, pp. 434.
  5. 1 2 Morrison, Brillhart, 1975.
  6. Маховенко, 2006, pp. 223.
  7. Kraitchik M. Théorie des Nombres. Tome I et II. — Paris:Gauthier-Villars. — 1926.
  8. 1 2 Нестеренко, 2012, pp. 173.
  9. Нестеренко, 2012, pp. 175.
  10. Ященко, 1999, pp. 113.
  11. 1 2 Нестеренко, 2012, pp. 178.
  12. 1 2 Ященко, 1999, pp. 112-113.
  13. Нестеренко, 2012, pp. 173,185.
  14. Манин, 1990, pp. 78.
  15. Маховенко, 2006, pp. 220.
  16. Маховенко, 2006, pp. 218-220.
  17. Кнут, 2013, pp. 439.
  18. Маховенко, 2006, pp. 219.
  19. Ященко, 1999, pp. 114.
  20. Нестеренко, 2012, pp. 172.
  21. 1 2 Маховенко, 2006, pp. 219-220.
  22. Нестеренко, 2012, pp. 176-177.
  23. Маховенко, 2006, pp. 221-222.
  24. Кнут, 2013, pp. 436.
  25. Pomerance, 1982.
  26. Василенко, 2003, pp. 87.

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