63
правки
Изменения
→Алгоритм
Нам нужен детерминированный алгоритм работающий за <tex>p(\log|n|)</tex>, где <tex>p</tex> {{---}} полином. Хоть и не существует такого эффективного детерминированного алгоритма, существует эффективный рандомизированный алгоритм.
Формально, нам нужно проверить принадлежит ли число языку <tex>PRIMES = \{ \llcorner N \lrcorner : N -</tex> простое <tex>\}</tex>. Предоставим алгоритм который покажет что <tex>PRIMES \in BPP</tex>. Для каждого <tex>N</tex> и <tex>A \in [1 .. N - 1]</tex>, определимсимвол Лежандра:
QR_N(A) =
\begin{cases}
0 & gcdA \equiv 0 \ (A, mod\ N) \ne 1\\ +1 & A = B^2 \not\equiv 0 \ (mod \ N), gcd\ \exists x: A \equiv x^2 \ (B, mod \ N) = 1\\
- 1, & \text{otherwise}
\end{cases}
</tex>
{{---}} Для каждого нечетного простого <tex>N</tex> и <tex>A \in [1 .. N - 1], QR_N(A) = A^{(\frac{N - 1)/}{2}} (mod N)</tex>{{---}} формула Лежандра
{{---}} Для каждого нечетного <tex>N, A</tex> определим симол Якоби <tex>(\frac{N}{A})</tex> как <tex>\prod\limits_{i=1}^k QR_{P(i)}(A)</tex>, где <tex>P_1, ... , P_k</tex> это простые делители (не обязательно различные) числа <tex>N (N = \prod\limits_{i=1}^k P_i)</tex>. Заметим что сивол Якоби вычислим за <tex>O(logA * logN)</tex>
{{---}} Для каждого нечетного составного <tex>N, |\{A \in [1\,..\,N - 1]: gcd(N, A) = 1 \,and\,(\frac{N}{A}) = A^{\frac{N - 1}{2}}\}| \le \frac{1}{2}</tex> <tex>\,| \{A \in [N - 1]: gcd(N, A) = 1\}|</tex>
