63
правки
Изменения
→Алгоритм
{{---}} Для каждого нечетного простого <tex>N</tex> и <tex>A \in [1 .. N - 1]</tex> выполняется: <tex>QR_N(A) = A^{\frac{N - 1}{2}} (mod \ N)</tex> {{---}} формула Лежандра
{{---}} Для каждого нечетного составного <tex>N, |\{A \in [1\,..\,N - 1]: gcd(N, A) = 1</tex> и <tex>(\frac{N}{A}) = A^{\frac{N - 1}{2}}\}| \le \frac{1N}{2}</tex> <tex>\,| \{A \in [1\,..\,N - 1]: gcd(N, A) = 1\}|</tex>
