Legendre-symbol-beregner

Om denne beregner

Legendre-symbolet (a/p), defineret for et heltal a og et ulige primtal p, er en kompakt måde at besvare et grundlæggende spørgsmål i talteorien: har kongruensen x² ≡ a (mod p) en løsning? Denne beregner evaluerer det med Eulers kriterium: (a/p) ≡ a^((p-1)/2) (mod p), som er lig med 1, hvis a er en kvadratisk rest modulo p, −1, hvis det er en ikke-rest, og 0, hvis p går op i a.

Legendre-symbolet er en byggesten i teorien om kvadratisk reciprocitet og optræder overalt i beregningsorienteret talteori og kryptografi — herunder primtalstest, algoritmer til beregning af modulære kvadratrødder og konstruktioner i elliptisk kurve-kryptografi — overalt hvor det har betydning, om et tal er et kvadrattal modulo et primtal.