Legendre-symbol-kalkulator

Om denne kalkulatoren

Legendre-symbolet (a/p), definert for et heltall a og et oddetallig primtall p, er en kompakt måte å besvare et grunnleggende spørsmål i tallteori: har kongruensen x² ≡ a (mod p) en løsning? Denne kalkulatoren beregner det med Eulers kriterium: (a/p) ≡ a^((p-1)/2) (mod p), som er lik 1 hvis a er en kvadratisk rest mod p, −1 hvis den er en ikke-rest, og 0 hvis p deler a nøyaktig.

Legendre-symbolet er en byggestein i teorien om kvadratisk resiprositet og dukker opp i hele beregningsorientert tallteori og kryptografi — blant annet i primtallstester, algoritmer for å beregne modulære kvadratrøtter og konstruksjoner i elliptisk kurve-kryptografi — overalt der det har betydning om et tall er et kvadrat modulo et primtall.