Math & Numbers

Проверка квадратичного вычета (символы Лежандра/Якоби)

Вычисляет символ Якоби (a/n) (нечётное n до 10¹⁸; для простого n это символ Лежандра): по простому модулю a^((n−1)/2) ≡ 1 означает квадратичный вычет, а Tonelli–Shanks (или прямая формула при p ≡ 3 (mod 4)) даёт корни ±√a; символ −1 гарантирует, что a — невыт. По составному модулю символ лишь необходим: −1 доказывает невычет, +1 ничего не гарантирует (при n ≤ 10⁵ ответ находится перебором). Классика: 10 — квадратичный вычет mod 13 с корнями ±6.