Legendre-symbol-kalkylator

Om denna kalkylator

Legendresymbolen (a/p), definierad för ett heltal a och ett udda primtal p, är ett kompakt sätt att besvara en grundläggande fråga inom talteorin: har kongruensen x² ≡ a (mod p) en lösning? Kalkylatorn beräknar den med Eulers kriterium: (a/p) ≡ a^((p-1)/2) (mod p), som är lika med 1 om a är en kvadratisk rest modulo p, −1 om det är en icke-rest och 0 om p delar a exakt.

Legendresymbolen är en byggsten i teorin om kvadratisk reciprocitet och dyker upp i hela den beräkningsinriktade talteorin och kryptografin – bland annat i primtalstester, algoritmer för att beräkna modulära kvadratrötter och konstruktioner inom elliptisk kurvkryptografi – överallt där det spelar roll om ett tal är en kvadrat modulo ett primtal.