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

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


Мы лишь кратко коснемся этой темы, отсылая читателей к книгам [,,]. Среди многих алгоритмов разложения мы выберем ту линию развития, которая привела к разложению числа, предложенного RSA.

Поиском эффективных способов разложения целых чисел на множители занимаются уже очень давно. Эта задача интересовала выдающихся ученых в области теории чисел. Вероятно Ферма был первый, кто предложил представить разлагаемое число в виде разности квадратов , а затем, вычисляя , попытаться найти нетривиальный делитель . Он же предложил и способ, позволяющий найти требуемое представление. Если разлагаемое число имеет два не очень отличающиеся по величине множителя, этот способ позволяет определить их быстрее, чем простой перебор делителей. Лежандр обратил внимание на то, что при таком подходе достаточно получить сравнение

(17)

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

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

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

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

(18)

из которого следует

(19)

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

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




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


[an error occurred while processing this directive]