Методы факторизации

Пусть N натуральное составное число. Требуется найти натуральные числа , для которых . Эта задача носит название задачи факторизации числа N. Следует заметить, что задача распознавания является ли данное число составным или простым сравнительно легко решается с помощью вероятностных тестов простоты типа Монте-Карло.

Теорема о распределении простых чисел. Пусть число простых чисел не превосходящих x. Например, =4 при х=10 (простые числа {2,3,5,7}). Оказывается простых чисел достаточно много.

Теорема о распределении простых чисел, доказанная в 1896 году Адамаром и независимо Валле Пуссеном, утверждает, что

при ,

то есть

,

Величина дает хорошее приближение к даже при небольших n. Например, при n=10⁹ погрешность приближения не превосходит 6%. Асимптотический закон позволяет оценить вероятность, с которой целое число, наугад выбранное из отрезка от 1 до n, является простым. Эта вероятность примерно равна 1/ln(n). В частности, для выбора простого числа нужно проверить на простоту в среднем проверить ln(n) случайно и равновероятно выбранных чисел. Например, чтобы найти простое число из 100 десятичных знаков, надо перебрать порядка ln10¹⁰⁰≈230 случайных чисел от 1 до 10¹⁰⁰. Заметим, что можно облегчить вычисления проверкой на простоту лишь нечетных чисел. Полезно также знать, что число десятичных знаков во взятом случайно и равновероятно числе из множества {1,2,3,…,10¹⁰⁰}c большой вероятностью близко к 100. Точнее, около 90% всех чисел имеют 100 знаков, 99,9% имеют 98 и более знаков.

Перебор делителей для определения простоты числа. Мы хотим узнать, является ли заданное число N простым? Известно, что разложение числа N на простые множители единственно. Здесь p₁<p₂<…<p_r и e_i – натуральные числа. Таким образом, задача состоит в том, чтобы узнать, состоит ли это разложение из единственного простого числа p₁.

Самый простой способ проверки – перебор делителей. Если N составное число, то N имеет простой делитель . Пытаемся разделить nна 2, 3,...,[ ] (чётные числа, большие 2 пропускаются). Если п не делится ни на одно из этих чисел, то оно простое. При этом можно исключить деление на составные числа. Так как при , то число делений N на простые числа до вычисления факторизации N не больше величины . При этом учитывают два обстоятельства. Во-первых, деление является сравнительно сложной операцией. Во-вторых, не известен эффективный способ построения последовательных простых чисел, кроме решета Эратосфена. А реализация этого метода требует большого объема памяти. Поэтому на практике для того, чтобы избежать многих лишних делений делят число N на числа из арифметических прогрессий

,

где произведение r первых простых чисел и . Конечно, сначала делят N на числа . Этот метод в раз быстрее, чем деление на все натуральные числа , так как в таком методе производится не более делений.

Псевдопростые числа. Достаточное условие не простоты числа N.

Обозначим через (Z/N)⁺ множество всех ненулевых вычетов по модулю N, а через (Z/N)* мультипликативную группу вычетов кольца (Z/N).

Если число N простое, то

Z⁺ = Z*.

Число N называется псевдопростым по основанию а из (Z/N)⁺, если выполнено утверждение малой теоремы Ферма:

а^N-1=1(modN).

Любое простое число Nявляется псевдопростым по любому основанию а Поэтому если удается найти основание а (Z/N)⁺, по которому Nне является псевдопростым, то число N – составное. На практике оказывается, что во многих случаях достаточно проверить основание а =2.

Итак, если 2^N-1≠1(modN), то N – составное число, в противном случае оно псевдопростое и возможно простое.

Оказывается, псевдопростые числа часто являются простыми числами.

Так:

· среди первых чисел до 10000 имеется только 22 «плохих чисел», то есть 22 псевдопростых числа по основанию 2 не являющихся простыми (первые из 22 «плохих» чисел: 341, 561, 645, 1105,…);

· доля «плохих» чисел среди к-значных стремится к нулю при к стремящимся к бесконечности;

· Доля составных чисел среди 50-разрядных псевдопростых по основанию 2 чисел (доля «плохих») не превосходит 10^-6, а среди 100 разрядных (доля «плохих») не превосходит 10^-13.

Для более точной проверки псевдопростого числа по модую 2 на простоту естественно использовать и другие модули. Но это не всегда помогает. Дело в том, что существуют так называемые числа Кармайкла – составные числа являющиеся псевдопростыми по любому основанию а из (Z/N)⁺. Числа Кармайкла встречаются очень редко. Первые из них это:561,1105, 1729. Их всего 255 среди первых 10⁸ натуральных чисел.

Тест Миллера-Рабина проверки числа на простоту. Напомним, что решение уравнения х²=1, не сравнимое с 1 и -1 по модулю N, называется нетривиальным квадратным корнем из 1 в кольце Z/N. Несложно доказывается, что если Z/N содержит нетривиальный корень из 1, то N – составное число. Действительно, если N=P простое число и для а Z/N и а²=1 modP, то а²=сP+1, то есть (а+1)(а-1)=сP. Это равенство не может выполняться при а {2,3,..,P-2}.

Тест Миллера-Рабина это вероятностный алгоритм проверки простоты числа N. Он проверяет соотношение

а^N-1=1(modN),

для нескольких значений а из (Z/N)⁺. Возводя а последовательно в степени тест проверяет не обнаруживается ли нетривиальный квадратный корень из 1 по модулю N. Если обнаруживается квадратичный корень, то тест прекращает работу с выводом, что N составное число. Тест также прекращает работу, если найдено а, при котором N не является псевдопростым. Для выработки чисел а из (Z/N)⁺ используется генератор случайных чисел. Число итераций теста s (число используемых а) фиксируется заранее.

Число а называют «удачным свидетелем», если тест при данном а сделал вывод о том, что N составное число. Ниже мы приводим утверждения о том, что для любого составного числа N не менее половины всех возможных а позволяет установить, что N – составное число. Точнее, среди элементов (Z/N)⁺ не менее (N-1)/2 являются свидетелями того, что N составное число. Таким образом, вероятность выбора удачного свидетеля (для составного N) превышает 0,5. Следовательно, вероятность принять составное число за простое за s итераций в тесте Миллера-Рабина не превышает . Более точно, Для нечетного N и для любого целого положительного s вероятность ошибки теста Миллера-Рабина не превосходит .

r-метод Полларда факторизации чисел. Выбирается многочлен над кольцом вычетов . Единственное требование к многочлену заключается в том, чтобы легко вычислялись его значения. Далее выбирают случайный вычет и вычисляют последовательность вычетов по правилу

, , ….., , …

На i -ом шаге вычисляют пару элементов последовательности. Далее вычисляют .

Возможны два варианта.

Если d=1, то вычисляют следующую пару .

Если , , то и – факторизация числа N.

Если d=N, то выбирают новое случайное или новый многочлен , и повторяют весь алгоритм с самого начала.

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

Идея доказательства состоит в следующем. Пусть N имеет делитель . Рассматривается последовательность вычетов . Видно, что элементы этой последовательности связаны соотношением . Предполагается, что последовательность выбирается независимо с равными вероятностями из . Тогда (см. § 6.5) число шагов до первого совпадения знаков последовательности оценивается сверху величиной с вероятностью при любом . Если это событие произошло, то минимальное i такое, что также не превосходит k. При этом показывается, что вероятность одновременного выполнения другого события очень мала, если конечно N не является степенью p. Пренебрегая этой вероятностью, получают

,

.

Значит, . Таким образом, в алгоритме требуется вычислять не более = элементов последовательности (так как ).

p-1 метод Полларда. Напомним предварительно некоторые понятия. Пусть – множество первых простых чисел, не превосходящих В. Множество S_B называется факторной базой. Из закона распределения простых чисел следует, что

.

Число x называется В-гладким, если оно разлагается в произведение простых чисел из факторной базы S_B.

Фиксируют параметр метода B>0. Полагают , где . Другой вариант выбора Т: . Метод заключается в реализации следующих двух шагов.

Шаг 1. Выбирают случайный вычет и вычисляют , .

Шаг 2. Вычисляют . Если , то увеличивают В. Если , то переходят к шагу 1 и выбирают новое а. Если для нескольких случайных а выполняется , то уменьшают В. Если , то и – факторизация числа N.

Замечают, что если р – простой делитель N и (p-1) – В-гладкое число, то . Действительно, если , то . Тогда, очевидно, и по малой теореме Ферма . Поэтому p делит .

Если для нескольких случайных а, то для любого простого делителя q числа N число q-1 является В-гладким. В этом случае уменьшают В с тем, чтобы суметь различить p и q.

Сложность метода определяется сложностью вычисления вычета . В случае применения бинарного метода возведения в степень получают оценку

умножений по mod N. Известно, что сложность умножения по mod N, как и сложность вычисления оценивается величиной двоичных операций.

Индекс-метод (метод случайных квадратов, алгоритм Диксона). Индекс – метод основан на вычислении вычетов , для которых . Показывают, что если N – нечетное составное число и для случайных выполнено , то с вероятностью не меньшей выполнено . Таким образом, в среднем надо найти не более двух пар таких вычетов для разложения N на множители.

Выбирают некоторое натуральное число В, параметр метода. Определяют – множество первых простых чисел, не превосходящих В. Значение параметра В выбирается таким образом, чтобы минимизировать сложность алгоритма.

Входные данные алгоритма. Нечетное составное число N.

Выходные данные алгоритма. Числа , для которых .

Шаг 1. Выбирают значение параметра В.

Шаг 2. Выбирают случайный вычет x, и вычисляют . Если , то и – факторизация числа N. Если , то выбирают другое x. Если , то вычисляют , .

Шаг 3. Проверяют число b на В-гладкость. Если b является В-гладким, то вычисляют каноническое разложение . Запоминают строку .

Повторяют шаг 2 и шаг 3 до тех пор, пока число найденных строк не превысит , где с – некоторая небольшая константа.

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

, (1)

. Полагают

,

.

По построению . Далее вычисляют . Если при этом не будет найдена факторизация N, то вычисляют другую нетривиальную линейную комбинацию (1). Всего таких комбинаций оказывается не менее . Если ни одна из них не приводит к факторизации N, то находят несколько новых разложений на шаге 2 и шаге 3 и повторяют шаг 4 с новыми строками до получения факторизации числа N. Алгоритм заканчивает свою работу.

Замечание.

1) Один из способов проверки В-гладкости вычетов b заключается в пробных делениях на простые числа и их степени .

2) Линейную комбинацию (1) можно вычислить, решив, например, систему линейных уравнений по mod 2 методом Гаусса.

3) Асимптотическая сложность алгоритма при оптимальном выборе натурального числа В равна (эта сложность набора системы линейных сравнений).

Развитие индекс-метода. Направления развития индекс-метода для факторизации больших целых чисел те же, что и направления развития индекс-метода для логарифмирования в простом поле. Рассмотрим здесь кратко метод непрерывных дробей и метод квадратичного решета. Тот и другой методы основаны на уменьшении величины чисел, проверяемых на гладкость на шаге 3 индекс – метода. Кроме того, метод квадратичного решета вместо пробных делений использует так называемую процедуру просеивания, которая значительно быстрее находит гладкие значения многочлена, в нашем случае квадратичного.

Метод непрерывных дробей. Замечено, что если научиться находить много таких , что вычет окажется по абсолютной величине существенно меньше N, например, (a – константа), то индекс – метод заработает значительно быстрее, так как при таком ограничении на b возрастет вероятность В-гладкости . Требуемые вычеты () получают исходя из того, что необходимые x ищут среди числителей подходящих дробей чисел . Для этого для небольших значений к=1,2,… вычисляют подходящие дроби числа , используя рекуррентный способ вычисления подходящих дробей квадратичных иррациональностей доказывают, что

.

Таким образом, в индексе – методе проводят следующее изменение. Вместо случайных x выбирают . Тогда, положив , получают

, .

Общая сложность такого алгоритма равна

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

.

Заметим, что в методе непрерывных дробей факторная база заметно меньше по размеру факторной базы первоначального варианта индекс – метода ( против ).

Идея метода квадратичного решета. Положим и . Доказывают, что . Рассматривают выражение

.

Показывают, что при справедлива оценка . При этом оказывается, что L небольшая по сравнению с N величина. Для случая, когда F(c) есть В-гладкое значение, то есть , получают сравнение

. (2)

Такие сравнения используются полностью аналогично случаю исходного индекс – метода. Для поиска В-гладких значений многочлена F(c) обычно применяют процедуру просеивания. Так как степень многочлена F(c) равна двум, то данный метод факторизации получил название метода квадратичного решета.

Матрица, составленная из строк показателей, с которыми простые q входят в разложение (2), является разреженной. Поэтому, для вычисления соотношения (1) применяют алгоритм Видемана или какой-либо другой метод решения разреженных систем. При

,

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

, (3)

где – вероятность В-гладкости числа F(c) при . Считают трудоемкость выполнения шага 4 индекс – метода. В итоге общая сложность алгоритма квадратичного решета выражается величиной при любом фиксированном .