= {,,...,}(p prim )
sind zyklisch, d.h. es existiert ein Element g , genannt Primitivwurzel, mit
= {g 0,g 1,...,g p - 2}.
Also existiert zu jedem x ein a {0,1,...,p - 2} mit
g a xp.
Dieses heißt Index oder diskreter Logarithmus von x zur Basis g und wird mit
g(x) bezeichnet.
Mit diesen zahlentheoretischen Hilfsmitteln können wir in der Tat iterierte Multiplikation auf iterierte Addition
zurückführen; denn ist
P > xi prim und g eine Primitivwurzel von
, so gilt
xi g g(xi) g g(xi)P.
Es stellt sich aber heraus, dass es nur für kleine m NC 1-Algorithmen zur Berechnung von xm oder des diskreten Logarithmus in m* gibt. Abhilfe schafft hier ein weiterer Satz der Zahlentheorie, der Chinesische Restsatz. Doch zuerst der
Eingabe: x = xi2i, m n Ausgabe: xm aim : = 2im NC 1 y : = xiaim (Es gilt y < n m ) NC 1 Berechne parallel y - i m für i = 0,...,n - 1 AC 0 Wähle das kleinste y - i m aus, das 0 ist, und gebe es aus.
Dabei werden die aim in der Konstruktionsphase für alle i = 0,...,m - 1 und m = 2,...,n berechnet und fest in den Schaltkreis eingebaut, alle anderen Schritte sind in NC 1.