Калькулятор символу Лежандра (Legendre)

Про цей калькулятор

Символ Лежандра (a/p), визначений для цілого числа a та непарного простого числа p, — це компактний спосіб відповісти на фундаментальне питання теорії чисел: чи має порівняння x² ≡ a (mod p) розв'язок? Цей калькулятор обчислює його за допомогою критерію Ейлера: (a/p) ≡ a^((p-1)/2) (mod p), що дорівнює 1, якщо a є квадратичним лишком за модулем p, −1, якщо це нелишок, і 0, якщо p ділить a націло.

Символ Лежандра є будівельним елементом теорії квадратичної взаємності і трапляється в усій обчислювальній теорії чисел і криптографії — зокрема в тестах простоти, алгоритмах обчислення квадратних коренів за модулем і побудовах в криптографії на еліптичних кривих, — скрізь, де важливо, чи є число повним квадратом за модулем простого числа.