Введение в криптографию
[an error occurred while processing this directive]

Как раскладывают составные числа на множители - часть 2


$" width="69" height="31" > будет удовлетворять () и с ее помощью можно надеяться получить разложение на простые множители.

В 1975 г. Моррисон и Бриллхарт стали перемножать сравнения () при различных с тем, чтобы таким способом получить квадрат целого числа в правой части. Этот метод, метод непрерывных дробей, позволил впервые разложить на множители седьмое число Ферма . Для реализации алгоритма выбирается так называемая база множителей . В нее входят ограниченные по величине некоторым параметром простые числа такие, что

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

На первом этапе алгоритма каждое очередное число делится на все числа

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

(20)

Этому номеру сопоставляется вектор (вектор показателей). Затем вычисляется следующее значение , и с ним проделывается в точности такая же процедура.

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

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

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

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




- Начало -  - Назад -  - Вперед -


[an error occurred while processing this directive]