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

Next: 4.8. Дискретное логарифмирование Up: 4. Алгоритмические проблемы теории Previous: 4.6. Как проверить большое Contents: Содержание

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

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

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

$\begin{displaymath} x^2\equiv y^2\pmod N. \end{displaymath}$ (17)

Конечно, не каждая пара чисел, удовлетворяющих ему, позволяет разложить

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

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

$\begin{displaymath} x_0=\xi, b_i=[x_i], x_{i+1}=\frac{1}{x_i-b_i},\ i=0, 1, 2,\dots. \end{displaymath}$

Лежандр доказал, что непрерывная дробь квадратичной иррациональности периодична. Если раскладывать в непрерывную дробь число $\xi=\sqrt{N}$ , то возникающие в процессе разложения числа

имеют вид $x_i=\dfrac{\sqrt{N}+P_i}{Q_i}$ с целыми

, причем всегда $0\leq P_i<\sqrt{N}$ , $0<Q_i<2\sqrt{N}$ . С каждой непрерывной дробью можно связать последовательность рациональных чисел, так называемых подходящих дробей, $\dfrac{A_i}{B_i}$ , $i\geq0$ , вычисляемых по правилам
$\begin{gather*} A_{i+1}=b_{i+1}A_i+A_{i-1}, \ B_{i+1}=b_{i+1}B_i+B_{i-1}, \ i\geq0,\\ A_0=b_0, B_0=A_{-1}=1, B_{-1}=0 \end{gather*}$
и стремящихся к разлагаемому числу. Если в непрерывную дробь разлагается число $\xi=\sqrt{N}$ , то справедливо соотношение

$\begin{displaymath} A_{i-1}^2-NB_{i-1}^2=(-1)^iQ_i, \end{displaymath}$

(18)

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

$\begin{displaymath} A_{i-1}^2\equiv(-1)^iQ_i\pmod N. \end{displaymath}$

(19)

Заметим, что длина периода разложения в непрерывную дробь числа $\xi=\sqrt{N}$ может быть большой и достигать величин порядка $\sqrt{N}$ .

В 1971 г. Шенкс предложил использовать сравнения (19) для конструирования чисел, удовлетворяющих (17). Если вычисления проводить до тех пор, пока при четном не получится при некотором целом , то пара чисел $\< A_{i-1}, R\>$ будет удовлетворять (17) и с ее помощью можно надеяться получить разложение на простые множители.

В 1975 г. Моррисон и Бриллхарт стали перемножать сравнения (19) при различных с тем, чтобы таким способом получить квадрат целого числа в правой части. Этот метод, метод непрерывных дробей, позволил впервые разложить на множители седьмое число Ферма $F_7=2^{128}+1$ . Для реализации алгоритма выбирается так называемая база множителей $\{p_1,p_2,\dots, p_s\}$ . В нее входят ограниченные по величине некоторым параметром простые числа такие, что $\genfrac{(}{)}{}{0}{N}{p_i}=1$ . Последнее условие связано с тем, что, согласно (18), в разложение на простые множители чисел могут входить лишь те простые, для которых является квадратичным вычетом.

На первом этапе алгоритма каждое очередное число делится на все числа $p_1,p_2,\dots, p_s$ и, если оно не разлагается полностью в произведение степеней этих простых, то отбрасывается. Иначе получается разложение

$\begin{displaymath} (-1)^iQ_i=(-1)^{a_0}\prod\limits_{j=1}^{s}p_j^{a_j}. \end{displaymath}$ (20)

Этому номеру

сопоставляется вектор $(a_0,a_1,\dots,a_s)$ (вектор показателей). Затем вычисляется следующее значение $Q_{i+1}$ , и с ним проделывается в точности такая же процедура.

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

$\begin{displaymath} \left(\prod_{i\in\Delta\hbox to0pt{\phantom{j}\hss}}^{\phan... ...ight)^2\equiv \left(\prod_{j=1}^{s}p_j^{b_j}\right)^2\pmod N. \end{displaymath}$

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

В этот алгоритм был внесен ряд усовершенствований: вместо $\sqrt{N}$ можно раскладывать в непрерывную дробь число $\sqrt{kN}$ , где маленький множитель подбирается так, чтобы в базу множителей вошли все малые простые; была предложена так называемая стратегия раннего обрыва и т.д. Сложность этого алгоритма была оценена в 1982 г. величиной $O(\exp(\sqrt{1{,}5\cdot\ln N\cdot\ln\!\ln N}))$ . При выводе этой оценки использовался ряд правдоподобных, но не доказанных гипотез о распределении простых чисел. Получившаяся в оценке функция растет медленнее любой степенной функции. Алгоритмы, сложность которых оценивается подобным образом, получили название субэкспоненциальных (в зависимости от $\ln N$ ).

В 1982 г. Померанцом был предложен еще один субэкспоненциальный алгоритм - алгоритм квадратичного решета. Его сложность оценивается такой же функцией, как и в методе непрерывных дробей, но вместо константы получена лучшая - . Обозначим $m=\left[\sqrt{N}\right]$ , и выберем ту же базу множителей, что и в методе непрерывных дробей. При малых целых значениях величина будет сравнительно невелика. Следующий шаг объясняет название алгоритма - квадратичное решето. Вместо того, чтобы перебирать числа и раскладывать соответствующие значения на множители, алгоритм сразу отсеивает негодные значения , оставляя лишь те, для которых имеет делители среди элементов базы множителей.

Задав некоторую границу , для каждого простого числа , входящего в базу множителей, и каждого показателя степени , с условием $p^a\leq B$ находим решения квадратичного сравнения $Q(x)\equiv 0\pmod{p^a}$ . Множество решений обозначим буквой $\Lambda$ . Итак, для каждого $x\in\Lambda$ найдется элемент базы множителей, а может быть и не один, входящий в некоторой степени в разложение на простые сомножители числа . Те числа , при которых значения оказываются полностью разложенными, дают нам вектор показателей, как и в алгоритме непрерывных дробей. Если таких векторов окажется достаточно много, с ними можно проделать те же операции, что и в алгоритме непрерывных дробей.

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

$\begin{displaymath} Q(x)=q_1q_2(-1)^{a_0}\prod_{j=1}^{s} p_j^{a_j} \pmod N. \end{displaymath}$ (21)

В нем допускается наличие двух дополнительных больших простых множителей

. Эти множители впоследствии при перемножении значений

исключаются.

Некоторые детали реализации алгоритма можно найти в работе [6]. Отметим здесь только, что на множители раскладывалось число , база множителей состояла из и 524338 простых чисел, меньших, чем . При этом было использовано $B_2=2^{30}$ . В результате просеивания получилось 112011 соотношений вида (21) без множителей , 1431337 соотношений с одним таким множителем и 6881138 соотношений с двумя множителями. Именно на поиск всех этих соотношений понадобились 220 дней и большое количество работавших параллельно компьютеров. На втором шаге алгоритма, когда из соотношений (21) комбинировались четные векторы показателей степеней, приходилось работать с матрицами, размеры которых измерялись сотнями тысяч битов. Этот второй шаг потребовал 45 часов работы. Уже четвертый вектор с четными показателями привел к искомому разложению на множители.