63
правки
Изменения
→Алгоритм
</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>. Cуществует алгоритм для вычисления символа Якоби за <tex>O(logA \cdot logN)</tex>. Можно посмотреть на [https://en.wikipedia.org/wiki/Jacobi_symbol википедии]
