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

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

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

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

при ,

то есть

,

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

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

Самый простой способ проверки – перебор делителей. Если 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.

Итак, если 2N-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 среди первых 108 натуральных чисел.

Тест Миллера-Рабина проверки числа на простоту. Напомним, что решение уравнения х2=1, не сравнимое с 1 и -1 по модулю N, называется нетривиальным квадратным корнем из 1 в кольце Z/N. Несложно доказывается, что если Z/N содержит нетривиальный корень из 1, то N – составное число. Действительно, если N=P простое число и для а Z/N и а2=1 modP, то а2=с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 метод Полларда. Напомним предварительно некоторые понятия. Пусть – множество первых простых чисел, не превосходящих В. Множество SB называется факторной базой. Из закона распределения простых чисел следует, что

.

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

Фиксируют параметр метода 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 индекс – метода. В итоге общая сложность алгоритма квадратичного решета выражается величиной при любом фиксированном .