next up previous
Next: Berechnung des iterierten Produkts Up: Division nach Beame, Cook Previous: Zahlentheoretische Grundlagen

Subsections

Chinesischer Restsatz

Seien p1,...,pm paarweise teilerfremde natürliche Zahlen und P : = $\prod_{i=1}^{m}$pi . Dann gibt es genau ein x $\epsilon$ $
\mathop {\bf Z}
$P mit
x1 $\textstyle\equiv$ x$\displaystyle
\mathop {\rm mod}
$p1   
x2 $\textstyle\equiv$ x$\displaystyle
\mathop {\rm mod}
$p2   
  $\textstyle\vdots$     
xm $\textstyle\equiv$ x$\displaystyle
\mathop {\rm mod}
$pm   

für x1 $\epsilon$ $
\mathop {\bf Z}
$p1,...,xm $\epsilon$ $
\mathop {\bf Z}
$pm . Sei vi $\epsilon$ $
\mathop {\bf Z}
$pi das Inverse zu ${\frac{P}{p_i}}$ modulo pi für alle i = 1,...,m , d.h.

vi $\displaystyle\cdot$ $\displaystyle{\frac{P}{p_i}}$ $\displaystyle\equiv$ 1$\displaystyle
\mathop {\rm mod}
$pi.

Dann gilt

x $\displaystyle\equiv$ $\displaystyle\sum_{i=1}^{m}$xi $\displaystyle\cdot$ vi $\displaystyle\cdot$ $\displaystyle{\frac{P}{p_i}}$$\displaystyle
\mathop {\rm mod}
$P.

Beweis hierfür:

x $\displaystyle\equiv$ xi $\displaystyle\cdot$ $\displaystyle\underbrace{v_i \cdot \frac P{p_i}}_{\equiv 1 
\mathop {\rm mod}
\nolimits p_i}^{}$ + $\displaystyle\sum_{j \not= i}^{}$$\displaystyle\underbrace{x_j \cdot v_j \cdot \frac P{p_j}}_{\equiv 0 
\mathop {\rm mod}
\nolimits p_i, \,{\rm da}\, p_j \vert P}^{}$$\displaystyle
\mathop {\rm mod}
$pi

Annahme:

Wir haben NC 1-Algorithmen, die P : = $\prod_{i=1}^{m}$pi und ${\frac{P}{p_i}}$ für i = 1,...,m berechnen.
Dann ist folgender Algorithmus, der den Chinesischen Restsatz anwendet, d.h. zu gegebenen paarweise teilerfremden

1 < p1 < p2 < ... < pm $\displaystyle\leq$ m 2

und

xi = (x$\displaystyle
\mathop {\rm mod}
$pi)$\displaystyle\qquad$(i = 1,..m)

x berechnet, korrekt und in NC 1:


 NC 1 $\qquad$  (1) Berechne 

 P : = $\prod_{i=1}^{m}$pi . 
 NC 1		      (2) 		 Berechne 

 ${\frac{P}{p_i}}$  für 

 i = 1,2,...,m  parallel. 
 NC 1		      (3) 		 Löse die Gleichungen 

 vi $\cdot$ ${\frac{P}{p_i}}$ $\equiv$ 1$\mathop {\rm mod}$pi  für  i = 1,...,m  parallel.
		 		      (Z.B. durch Ausprobieren) 
 NC 1		      (4) 		 Berechne 

 vi $\cdot$ ${\frac{P}{p_i}}$  für  i = 1,...,m  parallel. 
 NC 1		      (5) 		 Berechne 

 xi $\cdot$ vi $\cdot$ ${\frac{P}{p_i}}$  für  i = 1,...,m  parallel. 
 NC 1		      (6) 		 Berechne 

 y : = $\sum_{i=1}^{m}$xi $\cdot$ vi $\cdot$ ${\frac{P}{p_i}}$ 

Das gesuchte Ergebnis ist nun

y$\displaystyle
\mathop {\rm mod}
$P = y - t $\displaystyle\cdot$ Pt = $\displaystyle\left\lfloor \frac y P
 \right\rfloor.$

Im folgenden leiten wir uns die Berechnung von t her: Sei k die kleinste Zweierpotenz $\geq$ m , k = 2$\scriptstyle\lceil$$\scriptstyle\log_{2}$m$\scriptstyle\rceil$.

$\displaystyle{\frac{y}{P}}$ = $\displaystyle\sum_{i=1}^{m}$$\displaystyle{\frac{x_i v_i}{p_i}}$ = $\displaystyle{\textstyle\frac{1}{k}}$$\displaystyle\sum_{i=1}^{m}$$\displaystyle{\frac{k x_i v_i}{p_i}}$ $\displaystyle\geq$ $\displaystyle{\textstyle\frac{1}{k}}$$\displaystyle\sum_{i=1}^{m}$$\displaystyle\left\lfloor \frac{k x_i v_i}{p_i} \right\rfloor=$ : s $\displaystyle\Rightarrow$   
  $\textstyle\leq$ y - s $\displaystyle\cdot$ P = $\displaystyle{\textstyle\frac{1}{k}}$$\displaystyle\sum_{i=1}^{m}$$\displaystyle\underbrace{\left( \frac{k x_i v_i}{p_i} - \left\lfloor \frac{k x_i v_i}{p_i} \right\rfloor \right) }_{ < 1}^{}$P <   
  < $\displaystyle{\textstyle\frac{1}{k}}$$\displaystyle\sum_{i=1}^{m}$P = $\displaystyle\underbrace{\frac m k}_{\leq 1}^{}$P $\displaystyle\leq$ P   

Also gilt sicher: 0 $\leq$ y - $\lfloor$s$\rfloor$P < 2P . Damit erhalten wir t wie folgt:


1. Fall:      

 y - $\lfloor$s$\rfloor$P < P    $\Rightarrow$  

 t = $\lfloor$s$\rfloor$  
2. Fall: 		 

 y - $\lfloor$s$\rfloor$P $\geq$ P    $\Rightarrow$  

 t = $\lfloor$s$\rfloor$ + 1  

Fortsetzung des Algorithmus:


 NC 1 $\qquad$  (7)  Berechne 

 k $\cdot$ vi $\cdot$ xi  für  i = 1,...,m  parallel. 
  $\leq$ NC 1 (8) 		 Berechne 

 $\left\lfloor \frac{k \cdot v_i \cdot x_i}{p_i}\right\rfloor$  für  i = 1,...,m  parallel.
		 		 Da 

 pi = O(log m)  und 

 k $\cdot$ vi $\cdot$ xi = O(log m)  genügt ein
		 		 einfacher Divisionsalgorithmus mit maximal linearer
		 		 Komplexität (,,any reasonable division circuit``).
 NC 1		      (9) 		 Berechne 

 $\sum_{i=1}^{m}$$\left\lfloor \frac{k \cdot v_i \cdot x_i}{p_i}\right\rfloor$ .
 NC 0 (10) 		 Berechne 

 $\lfloor$s$\rfloor$ = $\left\lfloor \frac{ \sum_{i=1}^m\bigl\lfloor \frac{k \cdot v_i \cdot x_i}{p_i}\bigr\rfloor }m \right\rfloor$  (shift right). 
 NC 1		      (11) 		 if 

 y - $\lfloor$s$\rfloor$P < P  then 

 x : = y - $\lfloor$s$\rfloor$P  
 NC 1		 		 		 else 		 

 x : = y - $\left( \lfloor s \rfloor + 1 \right)P$ 

next up previous
Next: Berechnung des iterierten Produkts Up: Division nach Beame, Cook Previous: Zahlentheoretische Grundlagen
Andreas Abel
12/10/1997