А.В. Рожков, О.В. Ниссенбаум - Теоретико-числовые методы в криптографии (1127102), страница 20

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

Текст из файла (страница 20)

Будем говорить, что алгоритм обладает полиномиальной сложностью (по времени), если время его работы составляет O(n^k), то есть может быть ограничено сверху многочленом степени k для n>n₀ при некотором n₀.

Алгоритм, время работы которого составляет e^o(n), обладает субэкспоненциальной сложностью.

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

Полиномиальные по времени алгоритмы считаются эффективными, а задачи, решаемые такими алгоритмами, объединены в класс P.

Время работы субэкспоненциальных алгоритмов асимптотически выше, чем полиномиальных, но ниже, чем экспоненциальных.

Важным примером субэкспоненциальной функции является

L_q[α,c]=O(exp((c+o(1))ln^αq(ln ln q)^1-α)),

где c > 0, 0 < α < 1, q – длина входа.

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

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

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

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

§2. Алгоритмы факторизации.

Пусть n > 1. Требуется найти его разложение на простые сомножители , где p_i – простые числа (i = ), то есть факторизовать n.

Как было показано в Главе 1, с проблемой факторизации тесно связаны такие теоретико-числовые проблемы, как поиск квадратных корней по составному модулю (в том числе и проблема RSA), проблема распознавания квадратов и псевдоквадратов по модулю Блюма, проблема вычисления функции Эйлера. Было показано, что каждая из этих проблем не сложнее проблемы факторизации, а некоторые из проблем ей эквивалентны. Во всяком случае, решив задачу факторизации, дальнейшее решение каждой из этих проблем осуществляется за полиномиальное время.

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

Прежде чем приступить к факторизации числа, необходимо учесть следующее:

1) Если n – четное число, то следует выделить из него все степени двойки. Такая операция является легкой, особенно если число n представлено в двоичной форме. Тогда выделение степеней двойки – это битовый сдвиг вправо до тех пор, пока в младшем бите не появится «1».

2) Проверка на простоту проще, чем факторизация, поэтому прежде чем начать факторизацию нечетного n, следует проверить его на простоту.

3) Следует проверить, не является ли n целочисленной степенью какого-либо числа (n = x^k). Такая задача решается вычислением для всех целых k [2,log₂n] (если n предварительно проверено на четность, то k [2,log₃ n]).

4) Следует рассмотреть задачу 2-факторизации (сплиттинга), или расщепления n=a∙b (1<a,b<n)

Далее для всех алгоритмов полагаем, что n – составное число, нечетное и не степень целого числа.

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

На протяжении данного параграфа факторизуемое число будем обозначать n.

2.1. Метод пробных делений.

Этот метод является методом специального назначения и рекомендуется для отсеивания маленьких делителей на первом шаге. Если известно, что число не имеет малых делителей (например, модуль RSA), то этот метод не стоит применять.

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

Задается некая теоретическая граница B ≤ , которая задает максимальную величину испытываемых делителей и обусловливается доступным объемом памяти и вычислительными возможностями, а также некоторыми априорными сведениями о структуре числа n.

Если В невелико, то строим заранее таблицу простых чисел, меньших или равных В и проверяем делимость n на эти числа.

Иначе выбираем числа d₁=5, d₂=5+2=7, d₃=d₂+4=11, d₅=d₄+2, … , d_k > B. (чередуем шаг +2 и +4 с тем, чтобы отсеять числа, кратные «2» и «3»).

Эти d₁, … , d_k являются возможными делителями n. Осуществляем пробные деления на d_i (i = ). При этом действия осуществляются в следующем порядке:

Для каждого i:

Ш.1. Генерируем d_i.

Ш.2. Осуществляем пробное деление на d_i. Если d_i\n, то n=n/d_i и повторяем

Шаг 2. Если d_i не делит n, то идем на Шаг 3.

Ш.3. Уничтожаем d_i, освобождаем память.

Заметим, что все малые делители, выделенные вышеуказанным способом, будут простыми.

2.2. Метод Ферма.

Метод специального назначения, применяется для 2-факторизации, или сплиттинга.

Если n – нечетное составное число, не являющееся степенью целого числа, то этот метод находит целые числа x, y: n=x²—y² . Тогда n=(x+y)(x—y).

Алгоритм:

Ш.1. Вычисляем x= +1.

Ш.2. Если x= , то идем на Выход с сообщением «n – простое число».

Ш.3. Вычисляем z=x²—n и y= . Если y²=z, то идем на Выход, a=x+y, b=x—y.

Ш.4. Вычисляем x=x+1. Идем на Шаг 2.

Выход: n=a·b.

Отметим, что делители a и b, получившиеся в результате 2-факторизации Ферма, в общем случае не являются простыми и требуют проверки на простоту и дальнейшей факторизации.

2.3. Метод квадратичного решета.

Пусть n – число, которое надо факторизовать. Как и метод Ферма, данный метод ищет целые числа x, y: n=x²—y², но подход к поиску несколько иной. Поиск числа x осуществляется не среди всех чисел подходящего размера. Перед началом перебора производится отсев некоторых чисел.

Принцип отсева вытекает из следующих рассуждений: Возьмем небольшое число m и рассмотрим полную систему вычетов Z_m={0, 1, 2, … ,m—1}. Среди чисел из Z_m некоторые числа являются квадратами (то есть квадратичными вычетами), а другие не являются. Если m – простое число, то квадратов столько же, сколько неквадратов. Если m – составное, то квадратов несколько меньше. В общем случае,

P(s Q(m)) ≤ .

Если число не является квадратичным вычетом по какому-то модулю m, то оно не является квадратом в Z, поэтому число y² следует искать среди тех чисел, которые являются квадратами в Z_m.

В методе квадратичного решета берут несколько небольших попарно простых модулей m₁, m₂, … , m_k. Для каждого такого модуля составляют квадратичное решето (двоичный вектор S_m) следующим образом:

Для каждого x Z_m вычисляют x² mod m и z=(x²—n) mod m. Если z является квадратом по модулю m, то S_m(x)=1, иначе S_m(x)=0. Проверка того, является ли z квадратом по модулю m, производится путем сверки с вычисленными x² mod m.

X	0	1	2	…	m–1
x2mod m	0	1	22 mod m	…	(m–1)2mod m
z=x2–n mod m	1	1	z2	…	zm—1

После того, как все решёта построены, начинается отсев кандидатов x. Решёта накладываются на последовательность чисел x от +1 до . Те числа, на которые наложился «0» хотя бы одного решета, отсеиваются. После отсева остается достаточно небольшое количество чисел – кандидатов в x. Для каждого такого числа вычисляется x², z= x²–n и y= . Если y²=z, то числа a=x+y, b=x—y являются делителями числа n.

Пример:

n=279.

Построим решёта по модулям 4, 5 и 7:

x	0	1	2	3	4	5	6
x2mod 7	0	1	4	2	2	4	1
z=x2–279 mod 7	1	2	5	3	3	5	2
S7	1	1	0	0	0	0	1

Теперь, когда мы построили три решета, наложим их на последовательность чисел от +1=17 до =140.

Характеристики

Список файлов книги