5.1.1 Modular Arithmetic (Modulare Arithmetik)

5.1.1 Modular Arithmetic (Modulare Arithmetik)

Hinweise zur effizienten und sicheren Implementierung der Arithmetik modulo p = 2^255 - 19 finden sich in Curve25519 [CURVE25519]. Für die Inversion modulo p wird empfohlen, die Identität x^-1 = x^(p-2) (mod p) zu verwenden. 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“ werden Quadratwurzeln modulo p benötigt. Sie können mit dem Tonelli-Shanks-Algorithmus oder dem Spezialfall für p = 5 (mod 8) berechnet werden. Um eine Quadratwurzel von a zu finden, berechnet man zuerst die Kandidatenwurzel x = a^((p+3)/8) (mod p). Dann gibt es drei Fälle:

1. x^2 = a (mod p). Dann ist x eine Quadratwurzel.

2. x^2 = -a (mod p). Dann ist 2^((p-1)/4) * x eine Quadratwurzel.

3. a ist kein Quadrat modulo p.