Zahlentheoretische Grundlagen

Die multiplikativen Gruppen

$$\mathop {{\bf Z}_p^{*}}$$ = {$$\overline{1}$$,$$\overline{2}$$,...,$$\overline{p\!-\!1}$$}$$\qquad$$(p prim )

sind zyklisch, d.h. es existiert ein Element g $\epsilon$ $\mathop {{\bf Z}_p^{*}}$ , genannt Primitivwurzel, mit

$$\mathop {{\bf Z}_p^{*}}$$ = {g ⁰,g ¹,...,g ^{p - 2}}.

Also existiert zu jedem x $\epsilon$ $\mathop {{\bf Z}_p^{*}}$ ein a $\epsilon$ {0,1,...,p - 2} mit

g ^a $$\equiv$$ x$$\mathop {\rm mod}$$p.

Dieses heißt Index oder diskreter Logarithmus von x zur Basis g und wird mit $\mathop {\rm ind}$_g(x) bezeichnet.
Mit diesen zahlentheoretischen Hilfsmitteln können wir in der Tat iterierte Multiplikation auf iterierte Addition zurückführen; denn ist P > $\prod_{i=1}^{n}$x_i prim und g eine Primitivwurzel von $\mathop {{\bf Z}_p^{*}}$ , so gilt

$$\prod_{i=1}^{n}$$x_i $$\equiv$$ $$\prod_{i=1}^{n}$$g ^{$\mathop {\rm ind}$_g(x_i)} $$\equiv$$ g ^{$\sum_{i=1}^{n}$$\mathop {\rm ind}$_g(x_i)}$$\mathop {\rm mod}$$P.

Es stellt sich aber heraus, dass es nur für kleine m NC ¹-Algorithmen zur Berechnung von x$\mathop {\rm mod}$m oder des diskreten Logarithmus in $\mathop {\bf Z}$_m^* gibt. Abhilfe schafft hier ein weiterer Satz der Zahlentheorie, der Chinesische Restsatz. Doch zuerst der

Algorithmus zur Berechnung von x mod m für kleine m

Eingabe:    

 x = $\sum_{i=0}^{n-1}$xi2i,  m $\leq$ n  
Ausgabe: 		       

 x$\mathop {\rm mod}$m  
		      

 aim : = 2i$\mathop {\rm mod}$m  
 NC 1		      

 y : = $\sum_{i=0}^{n-1}$xiaim$\qquad$  (Es gilt 

 y < n $\cdot$ m ) 
 NC 1		      Berechne parallel 

 y - i $\cdot$ m  für 

 i = 0,...,n - 1  
 AC 0		      Wähle das kleinste 

 y - i $\cdot$ m  aus, das   $\geq$ 0 ist, und gebe es aus.

Dabei werden die a_im 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 ¹.