Простые числа

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

Пример: Анна и Борис начинают обмен сообщениями по открытому каналу связи и любой наблюдатель может перехватить и прочитать все их сообщения. Возможно ли для Анны передать секретное сообщение Борису так, что никакой наблюдатель не смог бы его прочесть? (Да)

Алгоритм RSA (Ривест, Шамир, Адлеман):

• Борис:

  1. придумать два (больших) простых числа \(p\) и \(q\), и вычислить \(N = p \cdot q\) и \(\phi(N) = \phi(p) \phi(q) = (p-1)(q-1)\)
  2. выбрать \(e < \phi(n)\) с условием \((e, \phi(n)) = 1\) и вычислить обратный к \(e\) по модулю \(\phi(N)\): \(e \cdot d \bmod \phi(N) = 1\)
  3. опубликовать публичный ключ \((N, e)\) и хранить секретный ключ \((N, d)\)

• Анна:

  1. зная публичный ключ Бориса \((N, e)\), зашифровать секретное сообщение \(m\) по формуле \(c = E(m) = m^e \bmod N\)

• Борис:

  1. получив сообщение \(c = m^e \bmod N\), расшифровать¹ сообщение \(m = D(c) = (m^e)^d \bmod N = m^{ed} \bmod N\)

Трудность для наблюдателя состоит в том, что при известном открытом ключе \((N, e)\) ему нужно как-то вычислить \(\sqrt[e]{c}\) по модулю \(N\). Другой возможностью является разложение на множители (факторизация) числа \(N = pq\) и последующее вычисление модуля \(\phi(N)\) для поиска \(d\). И то и другое является слишком трудной задачей для больших чисел и в настоящее время неизвестно быстрых алгоритмов ее решения.

Где взять большое простое число?

Теорема о распределении простых чисел утверждает, что в среднем расстояние между простыми числами растет как логарифм. Если выбрать случайно большое число \(n\) и рядом с ним произвольно выбирать числа, то вероятность попадания в простое число окажется около \(\frac{1}{\ln n}\).

Пример: для числа порядка \(n=2^{1024}\) потребуется проверить около \(\ln(n) \sim 710\) чисел.

Но как проверять, если речь о факторизации не идет?

Теорема. Число \(m > 1\) является простым числом тогда и только тогда, когда \(a^{m-1} \bmod m = 1\) для всех \(a \bmod m \neq 0\).

Для простого \(m\) утверждение выполняется по теореме Эйлера. Если же \(m\) составное, то найдется \(a < m\), делящее \(m\). Предположим, что и в этом случае \(a^{m-1} \bmod m = 1\). Тогда \(a\) делит \(m\) и \(m\) делит \(a^{m-1} - 1\). Следовательно, \(a\) делит \(a^{m-1} - 1\), что значит \(a^{m-1} - 1 = ak\) для некоторого \(k\) или \(a^{m-1} - a k = 1\), т.е. \(a\) делит \(1\). Противоречие.

С помощью этого факта можно быстро доказать, что число составное. Скажем, если \(2^{m-1} \bmod m \neq 1\), то число \(m\) составное. Возведение в степень (даже большую) выполняется очень быстро².

Но если для нескольких разных значений \(a\) увидеть этого не удалось, то возможно число \(m\) простое? Такое число называют вероятно простым.

Но вероятно простое число не обязательно является простым (то есть это вероятностный тест).

Пример числа, которое проваливает такой “тест”: \(2^{561-1} \equiv 1 \bmod 561\), но \(561 = 3 \cdot 11 \cdot 17\).

Другим вероятностным алгоритмом является тест простоты Миллера-Рабина. Он не сильно сложнее предыдущего в практическом применении и позволяет оценить вероятность “ложного срабатывания” (и быстро уменьшать ее с помощью повторного применения).

Алгоритм Миллера-Рабина:

определяет (вероятную) простоту числа \(n\) с помощью вычисления \(a^{n-1} \bmod n\) (как и в предыдущем примере, но с дополнительными проверками)

1. Выбрать число \(a\)
   (как и в предыдущем примере)
2. Представить число \(n-1 = 2^s \cdot d\), где \(d\) - нечетное
   (выделить степень двойки: тогда \(a^{n-1} = (a^d)^{2^s}\))
3. Вычислить \(x_0 = a^{d} \bmod n\)
4. Для каждого \(i=1, \ldots, s\) вычислять \(x_i = x_{i-1}^2 \bmod n = (a^d)^{2^i} \bmod n\);
   если \(x_i = 1\) и \(x_{i-1} \neq 1, n-1\) выдать "n СОСТАВНОЕ"
   (найден нетривиальный³ корень из 1)
5. Если \(x_s = (a^d)^{2^s} \bmod n = a^{n-1} \bmod n \neq 1\) выдать "n СОСТАВНОЕ";
   иначе выдать "n ПРОСТОЕ"