Теория остатков

Рефераты / Математика / Теория остатков

Такое число существует, поскольку $(e,\phi(m))=1$ , и притом единственно. Здесь и далее символом будет обозначаться наибольший общий делитель чисел и . Классическая теорема Эйлера, см. [3], утверждает, что для каждого числа , взаимно простого с , выполняется сравнение $x^{\phi(m)}\equiv1\pmod m$ и, следовательно,

$\begin{displaymath}a^d\equiv x^{de}\equiv x \pmod m.\end{displaymath}$

(4)

Таким образом, в предположении , единственное решение сравнения (2) может быть найдено в виде

$\begin{displaymath}x\equiv a^d\pmod m.\end{displaymath}$

(5)

Если дополнительно предположить, что число состоит из различных простых сомножителей, то сравнение (5) будет выполняться и без предположения . Действительно, обозначим и . Тогда $\phi(m)$ делится на $\phi(s)$ , а из (2) следует, что . Подобно (4), теперь легко находим $x\equiv a^d\pmod s$ . А кроме того, имеем $x\equiv 0\equiv a^d \pmod r$ . Получившиеся сравнения в силу дают нам (5).

Функция (1), принятая в системе RSA, может быть вычислена достаточно быстро. Как это сделать, мы обсудим чуть ниже. Пока отметим лишь, что обратная к функция $f^{-1}\colon x\mapsto x^d\pmod m$ вычисляется по тем же правилам, что и , лишь с заменой показателя степени на . Таким образом, для функции (1) будут выполнены указанные выше свойства а) и б).

Для вычисления функции (1) достаточно знать лишь числа и . Именно они составляют открытый ключ для шифрования. А вот для вычисления обратной функции требуется знать число , оно и является ``секретом'' , о котором речь идет в пункте в). Казалось бы, ничего не стоит, зная число , разложить его на простые сомножители, вычислить затем с помощью известных правил значение $\phi(m)$ и, наконец, с помощью (3) определить нужное число . Все шаги этого вычисления могут быть реализованы достаточно быстро, за исключением первого. Именно разложение числа на простые множители и составляет наиболее трудоемкую часть вычислений. В теории чисел несмотря на многолетнюю ее историю и на очень интенсивные поиски в течение последних 20 лет, эффективный алгоритм разложения натуральных чисел на множители так и не найден. Конечно, можно, перебирая все простые числа до $\sqrt{m}$ , и, деля на них , найти требуемое разложение. Но, учитывая, что количество простых в этом промежутке, асимптотически равно $2\sqrt{m}\cdot(\ln m)^{-1}$ , находим, что при , записываемом 100 десятичными цифрами, найдется не менее $4\cdot10^{42}$ простых чисел, на которые придется делить при разложении его на множители. Очень грубые прикидки показывают, что компьютеру, выполняющему миллион делений в секунду, для разложения числа $m>10^{99}$ таким способом на простые сомножители потребуется не менее, чем $10^{35}$ лет. Известны и более эффективные способы разложения целых чисел на множители, чем простой перебор простых делителей, но и они работают очень медленно. Таким образом, название статьи М. Гарднера вполне оправдано.