Calculator simbol Legendre

Despre acest calculator

Simbolul Legendre (a/p), definit pentru un număr întreg a și un număr prim impar p, este o modalitate compactă de a răspunde la o întrebare fundamentală din teoria numerelor: are congruența x² ≡ a (mod p) o soluție? Acest calculator îl evaluează folosind criteriul lui Euler: (a/p) ≡ a^((p-1)/2) (mod p), care este egal cu 1 dacă a este rest pătratic modulo p, −1 dacă este non-rest și 0 dacă p îl divide exact pe a.

Simbolul Legendre este o piatră de temelie a teoriei reciprocității pătratice și apare în toată teoria computațională a numerelor și în criptografie — inclusiv în testele de primalitate, în algoritmii pentru calculul rădăcinilor pătrate modulare și în construcții din criptografia pe curbe eliptice — oriunde contează dacă un număr este pătrat perfect modulo un număr prim.