63
правки
Изменения
→Алгоритм
</tex>
{{---}} Для каждого нечетного простого <tex>N, A</tex> определим симол Якоби и <tex>(\frac{N}{A})</tex> как <tex>\prod\limits_{i=in [1}^k QR_{P(i)}(A)</tex>, где <tex>P_1, ... , P_kN - 1]</tex> это простые делители (не обязательно различные) числа выполняется: <tex>N QR_N(N A) = A^{\prod\limits_frac{i=N - 1}^k P_i)</tex>. Cуществует алгоритм для вычисления символа Якоби за <tex>O{2}} (logA mod \cdot logNN)</tex>. Можно посмотреть на [https://en.wikipedia.org/wiki/Jacobi_symbol википедии]{{---}} формула Лежандра
{{---}} Для каждого нечетного составного <tex>N, |\{A \in [1\,..\,N - 1]: gcd(N, A) = 1</tex> и <tex>(\frac{N}{A}) = A^{\frac{N - 1}{2}}\}| \le \frac{1}{2}</tex> <tex>\,| \{A \in [1\,..\,N - 1]: gcd(N, A) = 1\}|</tex>
