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}}(mod \ N)\}| \le \frac{N}{2}</tex>
