5.2.1 Modular Arithmetic (Modulare Arithmetik)

5.2.1 Modular Arithmetic (Modulare Arithmetik)

Hinweise zur effizienten und sicheren Implementierung der Arithmetik modulo p = 2^448 - 2^224 - 1 finden sich in [ED448]. Zur Inversion modulo p wird die Identität x^-1 = x^(p-2) (mod p) empfohlen. Eine Inversion von Null sollte niemals vorkommen, da sie ungültige Eingaben erfordern würde, die zuvor erkannt worden wären, oder ein Rechenfehler wäre.

Für die Punktdekodierung oder „Dekompression“ sind Quadratwurzeln modulo p nötig. Sie können berechnet werden, indem zuerst die Kandidatenwurzel x = a ^ (p+1)/4 (mod p) bestimmt und dann geprüft wird, ob x^2 = a. Wenn ja, ist x die Quadratwurzel von a; wenn nein, besitzt a keine Quadratwurzel.