Эта статья входит в число добротных статей

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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

История[править | править вики-текст]

Метод непрерывных дробей был предложен Д. Г. Лемеромruen и Р. Е. Поверсом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]. Тогда из тех же простых чисел можно построить и .

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

,

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

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

,

где . Тогда .

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

Алгоритм[править | править вики-текст]

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

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

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

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

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

,

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

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

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

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

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

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

Некоторые улучшения[править | править вики-текст]

Пусть . Выше в непрерывную дробь раскладывалось число . Такой вариант эффективен, когда и близки друг к другу. Однако, чем больше разность между числами p и q, тем более трудоемким становится алгоритм. В этом случае вместо можно раскладывать в непрерывную дробь число , где маленький множитель k подбирается так, чтобы в базу множителей вошли все малые простые[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. Кнут, 2007, 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 Кнут, 2007, 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. Ященко, 2012, 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. Кнут, 2007, pp. 439.
  18. Маховенко, 2006, pp. 219.
  19. Ященко, 2006, pp. 114.
  20. Нестеренко, 2012, pp. 172.
  21. 1 2 Маховенко, 2006, pp. 219-220.
  22. Нестеренко, 2012, pp. 176-177.
  23. Маховенко, 2006, pp. 221-222.
  24. Кнут, 2001, pp. 436.
  25. Pomerance, 1982.
  26. Василенко, 2003, pp. 87.

Литература[править | править вики-текст]