Chinesischer Restsatz

Seien p₁,...,p_m paarweise teilerfremde natürliche Zahlen und P : = $\prod_{i=1}^{m}$p_i . Dann gibt es genau ein x $\epsilon$ $\mathop {\bf Z}$_P mit

$$\equiv \mathop {\rm mod}$$ x₁

$$\equiv \mathop {\rm mod}$$ x₂

$$\vdots$$

$$\equiv \mathop {\rm mod}$$ x_m

für x₁ $\epsilon$ $\mathop {\bf Z}$_p1,...,x_m $\epsilon$ $\mathop {\bf Z}$_pm . Sei v_i $\epsilon$ $\mathop {\bf Z}$_pi das Inverse zu ${\frac{P}{p_i}}$ modulo p_i für alle i = 1,...,m , d.h.

v_i $$\cdot$$ $${\frac{P}{p_i}}$$ $$\equiv$$ 1$$\mathop {\rm mod}$$p_i.

Dann gilt

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

Beweis hierfür:

x $$\equiv$$ x_i $$\cdot$$ $$\underbrace{v_i \cdot \frac P{p_i}}_{\equiv 1 \mathop {\rm mod} \nolimits p_i}^{}$$ + $$\sum_{j \not= i}^{}$$$$\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}^{}$$$$\mathop {\rm mod}$$p_i

Annahme:

Wir haben NC ¹-Algorithmen, die P : = $\prod_{i=1}^{m}$p_i 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 < p₁ < p₂ < ... < p_m $$\leq$$ m ²

und

x_i = (x$$\mathop {\rm mod}$$p_i)$$\qquad$$(i = 1,..m)

x berechnet, korrekt und in NC ¹:

 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$$\mathop {\rm mod}$$P = y - t $$\cdot$$ P, t = $$\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^{$\lceil$$\log_{2}$m$\rceil$}.

$${\frac{y}{P}} \sum_{i=1}^{m} {\frac{x_i v_i}{p_i}} {\textstyle\frac{1}{k}} \sum_{i=1}^{m} {\frac{k x_i v_i}{p_i}} \geq {\textstyle\frac{1}{k}} \sum_{i=1}^{m} \left\lfloor \frac{k x_i v_i}{p_i} \right\rfloor= \Rightarrow$$ =

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

$${\textstyle\frac{1}{k}} \sum_{i=1}^{m} \underbrace{\frac m k}_{\leq 1}^{} \leq$$ <

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$