Legendre-symbool calculator

Over deze rekenmachine

Het Legendre-symbool (a/p), gedefinieerd voor een geheel getal a en een oneven priemgetal p, is een compacte manier om een fundamentele vraag in de getaltheorie te beantwoorden: heeft de congruentie x² ≡ a (mod p) een oplossing? Deze calculator berekent het met het criterium van Euler: (a/p) ≡ a^((p-1)/2) (mod p), dat gelijk is aan 1 als a een kwadratisch residu mod p is, −1 als het een niet-residu is en 0 als p a precies deelt.

Het Legendre-symbool is een bouwsteen van de theorie van de kwadratische reciprociteit en komt overal voor in de computationele getaltheorie en cryptografie, onder meer bij priemtesten, algoritmen voor het berekenen van modulaire vierkantswortels en constructies in elliptische-kromme-cryptografie, overal waar het ertoe doet of een getal een volkomen kwadraat is modulo een priemgetal.