Генерация случайных простых чисел

Выбор случайных чисел основан на теореме Чебышева (для любого натурального n ⩾ 2 найдётся простое число p в интервале n < p < 2n)

Ввод: натуральное число \(N\ge 2\)
Вывод: случайное простое число из \((N,2N)\)

1. \(P\gets\) случайное число из \((N,2N)\)
2. Если \(P\) чётное, \(P\gets P+1\)
3. Пока \(P\) составное
   1. \(P\gets P+2\)
   2. Если \(P\ge 2N\) то \(P\gets N+1\), перейти к 2.
4. Конец

Алгоритм Евклида

Алгоритм Евклида позволяет достаточно эффективно найти НОД двух целых. Пусть ищется НОД(a,b), \(a > b\). Тогда можно построить последовательность \(r_0 > r_1 > r_2 > \ldots > r_n > 0\), удовлетворяющих уравнениям: \[r_0 = a\] \[r_1 = b\] \[\ldots\] \[r_i = r_{i-2} - r_{i-1}q_{i-1}\] \[\ldots\]

Здесь \[q_i = \left\lfloor \frac{r_{i-2}}{r_{i-1}} \right\rfloor\]

Тогда \(НОД(a, b) = r_n\).

То есть, \(r_i\) является остатком от деления двух предыдущих чисел в последовательности, а последний ненулевой член этой последовательности есть НОД.

Расширенный алгоритм Евклида дополнительно вычисляет последовательности \(s_i\) и \(t_i\): \[s_0=1\] \[s_1=0\] \[s_i = s_{i-2}-q_{i-1} s_{i-1}\] \[t_0=0\] \[t_1=1\] \[t_i = s_{i-2}-q_{i-1} s_{i-1}\]

Тогда \(s_n\) и \(t_n\) дают коэффициенты Безу: \[r_n = as_n + bt_n\]

Расширенный алгоритм Евклида можно использовать для вычисления мультипликативно-обратного. Чтобы мультипликативно-обратное числа \(a\) по модулю \(m\) существовало, \(a\) и \(m\) должны быть взаимно простыми. Тогда НОД = 1, и следовательно \[ms_n + at_n = 1,\] \[at_n = ms_n + 1,\] или \[at_n = 1 \pmod m,\] и тогда \(t_n\) – мультипликативно обратное к \(a\).

Детерминированные тесты простоты

Тест Агравала-Каяла-Саксены

Тест Аграва́ла-Кая́ла-Саксе́ны (AKS) – универсальный полиномиальный, детерминированный и безусловный тест простоты чисел, основанный на обобщении малой теоремы Ферма на многочлены.

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

Тест Адлемана-Померанса-Румели

Тест Адлемана-Померанса-Румели (APR) — эффективный, детерминированный и безусловный тест простоты чисел, разработанный в 1983 году.

Впоследствии алгоритм был улучшен Генри Коэном и Хендриком Ленстрой до APR-CL, временная сложность которого для любого числа \(n\) составляет \[O((\ln n)^{c\,\ln \,\ln \,\ln n}),\] где \(c\) — некоторая константа.

Тест Аткина-Морейна на эллиптических кривых (ECPP)

Универсальный алгоритм. В настоящее время ECPP на практике является самым быстрым из известных алгоритмов для проверки простоты чисел, но время выполнения в худшем случае неизвестно. Эвристическая оценка временной сложности составляет \[O((\log n)^{6+\varepsilon })\] для некого \(\varepsilon>0\).

Вероятностные тесты простоты

Тест Миллера-Рабина

Тест Миллера-Рабина – вероятностный полиномиальный тест простоты.

Основное утверждение теста формулируется следующим образом:

Пусть \(n\) — простое число и \(n-1=2^{s}d\), где \(d\) — нечётно. Тогда для любого \(a \in \mathbb N\), \(0 < a < n\) выполняется хотя бы одно из условий:

• \(a^{d} = 1 \pmod {n}\)
• \(\exists r \in \mathbb Z, 0 \le r < s:\) \[a^{2^{r}d} = -1\pmod {n}\]

Идея в следующем: если хотя бы одно из условий выполняется для чисел \(a\) и \(n\), то \(a\) называется свидетелем простоты по Миллеру. Если найдётся число, для которого оба условия не выполняются, то \(n\) – составное.

Рабин доказал, что у нечётных составных \(n\) не более \(\varphi(n)/4\) свидетелей простоты. Тогда для составного числа вероятность случайно выбрать свидетеля простоты не больше ¼. Тогда \(k\) раз случайно выбирая различные \(a<n\), если все они окажутся свидетелями простоты, вероятность того, что \(n\) составное не больше \(2^{-2k}\).

При проверке второго условия при помощи возведения в квадрат в цикле, сложность алгоритма составляет \(O(k \log^3 n)\). Эффективная реализация умножения (например алгоритм Шёнхаге-Штрассена или алгоритм Фюрера) может ещё несколько уменьшить сложность.

Тест Соловея — Штрассена

Тест Соловея — Штрассена — вероятностный тест простоты.

Основное утверждение теста формулируется следующим образом.

Если \(n\) – нечётное составное число, то количество целых чисел \(a\), взаимно простых с \(n\) и меньших \(n\), удовлетворяющих соотношению \[a^{(n-1)/2} = \left( \frac{a}{n} \right) \pmod n,\tag{*}\] не превосходит \(n/2\), где \(\left( \frac{a}{n} \right)\) – символ Якоби.

\[\left(\frac{a}{n}\right) = \left(\frac{a}{p_1}\right)^{\alpha_1}\left(\frac{a}{p_2}\right)^{\alpha_2}\cdots \left(\frac{a}{p_k}\right)^{\alpha_k},\] где \(n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}\) – разложение \(n\) на простые множители, а

\[\left(\frac{a}{p}\right) = \begin{cases} 0, & a = 0 \pmod{p},\\ 1, & a \neq 0\pmod{p}, \exists x \in \mathbb Z :a= x^2\pmod{p},\\ -1, & \text{иначе} \end{cases}\] \(\left(\frac{a}{1}\right) = 1.\)

Идея в том, чтобы провести \(k\) проверок этого утверждения.

В каждом раунде случайным образом выбирается число \(a < n\). Если \(НОД(a,n) > 1,\) то n – составное.

Иначе, проверяется справедливость сравнения \((\text{*})\), если оно не выполняется, то \(n\) — составное.

Если сравнение выполняется, то \(a\) – свидетель простоты \(n\).

После нахождения \(k\) свидетелей простоты, \(n\) является составным с вероятностью \(2^{-k}\).

Вычисление символа Якоби

Символ Якоби не вычисляется по определению. Вместо этого, существует эффективный алгоритм, аналогичный алгоритму Евклида, основанный на свойствах символа Якоби.

Свойства \(\left( \frac{a}{n} \right)\):

1. Если \(a = b \pmod n\), то \(\left( \frac{a}{n} \right) = \left( \frac{b}{n} \right)\)
2. \(\left( \frac{2a}{n} \right) = \left( \frac{2}{n} \right) \left( \frac{a}{n} \right)\), \[\left( \frac{2a}{n} \right) = \begin{cases} \left( \frac{a}{n} \right), & n = 1, 7 \mod 8 \\ -\left( \frac{a}{n} \right), & n = 3, 5 \mod 8 \\ \end{cases}\]
3. \(\left( \frac{ab}{n} \right) = \left( \frac{a}{n} \right)\left( \frac{b}{n} \right)\)
4. \(\left( \frac{a}{n} \right) = \begin{cases} 0, & НОД(a,n) \neq 1 \\ \pm 1, & НОД(a,n) = 1 \end{cases}\)
5. Если \(n>0\), \(m>0\), \(НОД(m,n) = 1\), то \[\left( \frac{m}{n} \right) \left( \frac{n}{m} \right) = (-1)^{(m-1)(n-1)/4} =\begin{cases} -1, & n = m = 3 \mod 4 \\ 1, & \text{иначе} \end{cases}\]

Для вычисления \(\left( \frac{a}{n} \right)\)

1. \(a \leftarrow a \mod n\) (по св-ву 1)
2. Если \(a\) чётное, преобразовать по св-ву 2.
3. Если \(a = 1\), то вернуть \(1\) (по св-вам 3,4); Если \(НОД(a,n) \neq 1\), то вернуть 0 (по св-ву 4)
4. По свойству 5, поменять \(a\), \(n\) местами, перейти к шагу 1.