Next: Literatur Up: Division nach Beame, Cook Previous: Chinesischer Restsatz

Berechnung des iterierten Produkts


Eingabe:   n   n -bit-Zahlen  x₁,...,x_n  
Ausgabe:  		Produkt 

 x_i

Konstruktionsphase:

Ermittle m paarweise verschiedene Primzahlen 1 < p₁ < p₂ < ... < p_m $\leq$ n² mit
P : = $\displaystyle\prod_{i=1}^{m}$ p_i $\displaystyle\geq$ 2^n² > $\displaystyle\prod_{i=1}^{n}$ x_n
(immer möglich für n > 5 ).
Ermittle einen Generator (Primitivwurzel) g_i für $\mathop {\bf Z}$ _{p_i}^* 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¹  Berechne 

 x_ip_j  für 

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

 l_ij : = _{g_j}(x_ip_j)  
 NC¹		 Berechne die Summen 

 S_j : = l_ij . 
 AC⁰		 Lese die Anti-Logarithmen aus 

 y_j : = g_j^S_j. 
 NC¹		 Berechne 

 y : = x_i  durch Anwendung des
		 Chinesischen Restsatzes auf 

 y₁,...,y_m .

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) .

Next: Literatur Up: Division nach Beame, Cook Previous: Chinesischer Restsatz

Andreas Abel
12/10/1997