5. Quadratwurzeln und quadratische Symbole

Wir werden Quadratwurzeln modulo Primzahlen mit Hilfe von primitiven Wurzeln und Exponenten berechnen. Dies unterscheidet sich etwas von der Methode, die in vielen Referenzen verwendet wird, aber wir möchten betonen, dass die Welt der additiven Exponentenarithmetik wichtig ist. Modulo einer Primzahl p arbeiten die Exponenten additiv modulo \(p-1\). Wenn wir zur RSA-Verschlüsselung kommen, bei der wir einen Modulus \(N = pq\) für zwei große und unbekannte Primzahlen p und q haben, können wir nicht die gleichen Exponentenspiele wie bei Primzahlen spielen, weil \(\phi (N) = (p-1)(q-1)\) nicht \(N-1\) ist, und es ist das \(\phi (N)\), das die Arithmetik auf den Exponenten bestimmt. In den späteren Kapiteln über Faktorisierung und elliptische Kurven wird es rechnerisch vorteilhaft sein, bestimmen zu können, ob eine Zahl kongruent zu einem Quadrat modulo eines Modulus N ist oder nicht. Glücklicherweise kann festgestellt werden, ob eine Zahl ein Quadrat modulo einer Primzahl ist, oder festgestellt werden, dass eine Zahl kein Quadrat modulo einer zusammengesetzten Zahl ist, durch einen Prozess, der dem ggT ähnelt und die gleiche logarithmische Komplexität hat.