Legendre-Symbol-Rechner

Über diesen Rechner

Das Legendre-Symbol (a/p), definiert für eine ganze Zahl a und eine ungerade Primzahl p, ist eine kompakte Art, eine grundlegende Frage der Zahlentheorie zu beantworten: Hat die Kongruenz x² ≡ a (mod p) eine Lösung? Dieser Rechner wertet es mit dem Euler-Kriterium aus: (a/p) ≡ a^((p-1)/2) (mod p), das 1 ergibt, wenn a ein quadratischer Rest modulo p ist, −1, wenn es ein Nichtrest ist, und 0, wenn p die Zahl a teilt.

Das Legendre-Symbol ist ein Baustein der Theorie des quadratischen Reziprozitätsgesetzes und taucht in der gesamten algorithmischen Zahlentheorie und Kryptografie auf – darunter Primzahltests, Algorithmen zur Berechnung modularer Quadratwurzeln und Konstruktionen der Kryptografie mit elliptischen Kurven –, überall dort, wo es darauf ankommt, ob eine Zahl modulo einer Primzahl ein perfektes Quadrat ist.