Berechnung des iterierten Produkts

Eingabe:   n   n -bit-Zahlen  x1,...,xn  
Ausgabe:  		Produkt 

 $\prod_{i=1}^{n}$xi 

Konstruktionsphase:

• Ermittle m paarweise verschiedene Primzahlen 1 < p₁ < p₂ < ... < p_m $\leq$ n ² mit

  P : = $$\prod_{i=1}^{m}$$p_i $$\geq$$ 2ⁿ² > $$\prod_{i=1}^{n}$$x_n

  (immer möglich für n > 5 ).
• Ermittle einen Generator (Primitivwurzel) g_i für $\mathop {\bf Z}$_pi^* und eine Tabelle der diskreten Logarithmen

  g_i⁰,g_i¹,...,g_i^{p_i - 2}

  für i = 1,...,m .
• Berechne ${\frac{P}{p_i}}$ = $\prod_{j \not= i}^{}$p_j und v_i , das Inverse zu ${\frac{P}{p_i}}$ modulo p_i .

Alle diese Werte werden fest in den Schaltkreis integriert.

Eigentlicher Schaltkreis (Berechnungen zur Laufzeit):

 NC 1  Berechne 

 xi$\mathop {\rm mod}$pj  für 

 i = 1,...,n,j = 1,...,m  parallel. 
 AC 0		 Lese die diskreten Logarithmen aus
		 

 lij : = $\mathop {\rm ind}$gj(xi$\mathop {\rm mod}$pj)  
 NC 1		 Berechne die Summen 

 Sj : = $\sum_{i=1}^{n}$lij . 
 AC 0		 Lese die Anti-Logarithmen aus 

 yj : = gjSj. 
 NC 1		 Berechne 

 y : = $\prod_{i=1}^{n}$xi  durch Anwendung des
		 Chinesischen Restsatzes auf 

 y1,...,ym .

Damit hätten wir den NC ¹-Schaltkreis für Ganzzahl-Division vollständig realisiert. Da die Konstanten P und v_i $\cdot$ ${\frac{P}{p_i}}$ vorausberechnet werden müssen, ist der Schaltkreis nicht log space-uniform, nur P-uniform, d.h. kann auf einer Turingmaschine mit polynomialem Platz auf dem Arbeitsband konstruiert werden. Es wurden jedoch auch log space-uniforme Schaltkreise gefunden, nur sind diese nicht in NC ¹, sondern haben die Tiefe O(lognlog log n) .