x1 | xp1 | ||
x2 | xp2 | ||
xm | xpm |
für x1 p1,...,xm pm . Sei vi pi das Inverse zu modulo pi für alle i = 1,...,m , d.h.
vi 1pi.
Dann gilt
x xi vi P.
x xi + pi
1 < p1 < p2 < ... < pm m 2
und
xi = (xpi)(i = 1,..m)
x berechnet, korrekt und in NC 1:
NC 1 (1) Berechne P : = pi . NC 1 (2) Berechne für i = 1,2,...,m parallel. NC 1 (3) Löse die Gleichungen vi 1pi für i = 1,...,m parallel. (Z.B. durch Ausprobieren) NC 1 (4) Berechne vi für i = 1,...,m parallel. NC 1 (5) Berechne xi vi für i = 1,...,m parallel. NC 1 (6) Berechne y : = xi vi
Das gesuchte Ergebnis ist nun
yP = y - t P, t =
Im folgenden leiten wir uns die Berechnung von t her: Sei k die kleinste Zweierpotenz m ,
k = 2m.
= | = : s | ||
y - s P = P < | |||
< | P = P P |
Also gilt sicher: 0 y - sP < 2P . Damit erhalten wir t wie folgt:
1. Fall: y - sP < P t = s 2. Fall: y - sP P t = s + 1
NC 1 (7) Berechne k vi xi für i = 1,...,m parallel. NC 1 (8) Berechne für i = 1,...,m parallel. Da pi = O(log m) und k vi xi = O(log m) genügt ein einfacher Divisionsalgorithmus mit maximal linearer Komplexität (,,any reasonable division circuit``). NC 1 (9) Berechne . NC 0 (10) Berechne s = (shift right). NC 1 (11) if y - sP < P then x : = y - sP NC 1 else x : = y -