Kalkulator symbolu Legendre'a

O tym kalkulatorze

Symbol Legendre’a (a/p), zdefiniowany dla liczby całkowitej a i nieparzystej liczby pierwszej p, to zwięzły sposób odpowiedzi na fundamentalne pytanie teorii liczb: czy kongruencja x² ≡ a (mod p) ma rozwiązanie? Ten kalkulator oblicza go za pomocą kryterium Eulera: (a/p) ≡ a^((p-1)/2) (mod p), co daje 1, jeśli a jest resztą kwadratową modulo p, −1, jeśli jest nieresztą, oraz 0, jeśli p dzieli a.

Symbol Legendre’a jest elementem składowym teorii wzajemności kwadratowej i pojawia się w całej obliczeniowej teorii liczb i kryptografii — w tym w testach pierwszości, algorytmach obliczania pierwiastków kwadratowych modulo i konstrukcjach w kryptografii krzywych eliptycznych — wszędzie tam, gdzie liczy się, czy liczba jest kwadratem doskonałym modulo liczba pierwsza.