Systemy resztowe
Kongruencje
Liczby kongruentne (przystaj ce) modulo w" (w  moduł przystawania)
"(N,M" ): Na"M(modw) Ô! "k" : N-M=kw (" M-N=kw
Kongruencja  relacja równowa no ci:
" zwrotna (reflexive): Na"N(modw),
" symetryczna (symmetric): Na"M(modw)Ô!Ma"N(modw),
" przechodnia (transitive): Na"M(modw)&Ma"P(modw)Ò!Na"P(modw).
LEMAT: Kongruencja jest zachowawcza (oboj tna, indifferent) wobec ka dego
z działa : dodawania, odejmowania, mno enia (f&)
Na"M(modw)'"Qa"P(modw)Ò!Nf&Qa"Mf&P(modw).
DOWÓD: Je li N=M+aw oraz Q=P+bw, to NąQ=(MąP)+(aąb)w
oraz NQ=MP+(śb+Pa+abw)w
Iloraz całkowity Xdivw (w"
"X" : X-Xmodw=wÅ"Xdivw

© Janusz Biernat, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009 RNS 1
Systemy resztowe
Klasy kongruencji
Klasy kongruencji (równowa no ci wzgl dem relacji przystawania)
={Z" :Za"r(modw); ðÅ‚-w/2ûÅ‚d"r<ðÅ‚w/2ûÅ‚}, *" *"
&
w:r w:0 w:1 w:r 1
r  reszta z dzielenia (residue) liczby całkowitej (naturalnej) przez moduł w
najmniej odległa od zera (najmniejsza bezwzgl dnie)
W zbiorze liczb naturalnych jest re"0 i mamy: ‚" (" ‚"
w:r w:r w:r w:r w
" ={5,12,19,26,& } ‚" ={& , 9, 2,5,12,19,26,& }
7:5 7: 2
" ={1,8,15,22,& } ‚" ={& , 13, 6,1,8,15,22,& }
7:1 7:1
DEFINICJE
Podzielnik p" liczby Q"
p|Q Ô! Qmodp=0, p"
Odwrotno (multyplikatywna) x 1 modw liczby x modulo w
a=x 1 modw Ô! ax modw=1
! (je li x i w maj wspólny podzielnik p`" 1, to zÅ"xmodw=1 nie ma rozwi zania)

© Janusz Biernat, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009 RNS 2
Systemy resztowe
Algorytm Euklidesa
Najwi kszy wspólny (po)dzielnik NWD (greatest common divisor, GCD)
NWD(X,Y)=a" Ô! (a|X '"a|Y ) '" Ź"b" : (b>a)'"(b|X '"b|Y )
TWIERDZENIE:
Dla dowolnych liczb naturalnych n i m, je li m1. liczba p jest te najwi kszym wspólnym dzielnikiem m oraz nmodm.
2. istniej takie liczby całkowite u oraz v, e p=un+vm (najwi kszy wspólny
dzielnik mo na przedstawi jako kombinacj liniow liczb m oraz n).
DOWÓD:
1. Je li p=NWD(m,n), to m=kmp oraz n=knp , to n-m=(kn-km)p , wi c
m2. Je li p=NWD(n,m), to m=kmp, n=knp oraz NWD(kn,km)=1. Mamy zatem
vm=vkmp, un=uknp i vkm+ukn=1. Poniewa NWD(kn,km)=1, wi c ka da
liczba ukn dla u=1,2,& ,km-1 nale y do innej klasy kongruencji modulo km.
Istnieje wi c takie u, e ukn=skm+1. Równo jest spełniona gdy v=-s.

© Janusz Biernat, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009 RNS 3
Systemy resztowe
WÅ‚a ciwo ci reszt
Liczby wzgl dnie pierwsze (relatively prime): NWD(X,Y )=1.
LEMAT:
Je eli reszty z dzielenia liczby przez moduły wzgl dnie pierwsze s sobie równe,
to s one równe reszcie z dzielenia przez iloczyn tych modułów
(w1, w2 ) = 1 & X mod w1 = X mod w2 = q Ò! X mod(w1w2 ) = q.
DOWÓD:
Je li Xmodw1=q i Xmodw2=q, to (X q)modw1=0 i (X q)modw2=0. Zatem
X q=k1w1 i X q=k2w2, wi c X q=k w1w2 oraz Xmodw1w2=q
LEMAT: Kongruencje mo na dzieli obustronnie przez wspólny czynnik:
(aX)mod(aw)=a(Xmodw)
DOWÓD:
(aX)mod(aw)=aX-awðÅ‚aX/awûÅ‚=a(X-wðÅ‚X/wûÅ‚)=a(Xmodw)

© Janusz Biernat, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009 RNS 4
Systemy resztowe
Sito Eratostenesa
Je li z ci gu kolejnych liczb naturalnych usuniemy
podzielne przez 2 (parzyste), nast pnie
podzielne przez 3 (co trzeci ), nast pnie
podzielne przez 5 (co pi t spo ród wszystkich) etc.,
to w ci gu pozostan tylko liczby pierwsze.
Je li a|N oraz a>N/a, to w ci gu N kolejnych liczb naturalnych
nie ma ju liczb podzielnych przez a (zostały wcze niej wykre lone)
Wszystkie liczby pierwsze (oprócz  2 ) s nieparzyste
Algorytm:
1. Utwórz ci g kolejnych liczb nieparzystych 2. Znajd w ci gu pierwsz liczb A ró n od 1 (jest na pozycji A0=(A+1)/2)
3. W miejsce ka dej liczby ci gu umieszczonej na pozycji A0+kA wpisz 0
4. Je eli A2Najmniejsza wspólna wielokrotno NWW(least common multiply, LCM)
NWW(X1, X2,& , Xm)=W" Ô! "i: Xi|W '" Ź"Z" : (Z
© Janusz Biernat, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009 RNS 5
Systemy resztowe
Podzielno liczb (1)
k -1 k -1
ëÅ‚ öÅ‚mod w = ëÅ‚
i i
xi²
ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚
" "(x mod w)(² mod w)öÅ‚mod w,
i
íÅ‚ i=0 Å‚Å‚ íÅ‚ i=0 Å‚Å‚
i i
ale ² mod(² Ä…1) = m1 Ò! ² mod(² Ä…1) = (m1) ,
wi c, poniewa 0d"xid"² 1, mamy
k -1 k -1
ëÅ‚ öÅ‚mod (² -1) = ëÅ‚
i
xi² xi öÅ‚mod (² -1)
ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚
" "
íÅ‚ i=0 Å‚Å‚ íÅ‚ i=0 Å‚Å‚
k -1 k -1
ëÅ‚ öÅ‚mod (² +1) = ëÅ‚
i i
xi²
ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚
" "(-1) xi öÅ‚mod (² +1)
íÅ‚ i=0 Å‚Å‚ íÅ‚ i=0 Å‚Å‚
Ò! reguÅ‚y podzielno ci przez 9 i 11 w systemie dziesi tnym
785 mod 9 = (7+8+5) mod 9 = 2 , 785 mod 11 = (7 8+5) mod 11 = 4
k
Je li ²=akÄ…1, to ² mod a = Ä…1 oraz ² mod a = (Ä…1)k
Ò! reguÅ‚y podzielno ci przez a w systemie o bazie ²=akÄ…1
785 mod 3 = (7+8+5) mod 3 = 20 mod 3 = 2

© Janusz Biernat, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009 RNS 6
Systemy resztowe
Podzielno liczb (2)
n-1
k
îÅ‚n / k Å‚Å‚-1 -1 îÅ‚n / k Å‚Å‚-1
i s k
( = Xi k i,
²
"x ² = " "x ² )(² )i "
i ik + s
i=0 i=0 s=0 i=0
k -1
gdzie Xi = xik +l s s warto ciami cyfr po konwersji (² ² k). Ale jest
²
"
s=0
k k kj k j
² mod(² Ä…1) = m1Ò! ² mod(² Ä…1) = (m1) , zatem:
ëÅ‚ öÅ‚
ëÅ‚n-1 öÅ‚mod (² -1) = ìÅ‚ îÅ‚n / k Å‚Å‚-1
i k k
Xi ÷Å‚mod (² -1)
ìÅ‚ ÷Å‚
"x ² Å‚Å‚ "
i
ìÅ‚ ÷Å‚
íÅ‚i=0 i=0
íÅ‚ Å‚Å‚
ëÅ‚ öÅ‚
ëÅ‚n-1 öÅ‚mod (² +1) = ìÅ‚ îÅ‚n / k Å‚Å‚-1
i k k
(-1)i Xi ÷Å‚mod (² +1)
ìÅ‚ ÷Å‚
"x ² Å‚Å‚ "
i
ìÅ‚ ÷Å‚
íÅ‚i=0 i=0
íÅ‚ Å‚Å‚
" 453310 mod 10110 = 453310 mod (102+1)10 = (33-45) mod (102+1)10 = -1210
" 53316 mod 0FF16 = 53316 mod (102-1)16 = (33+5)16 mod (102-1)16 = 3816
" 110111011102 mod 778 = 23568 mod (102-1)8 = (23+56)8 mod (102-1)8 = 28

© Janusz Biernat, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009 RNS 7
Systemy resztowe
Okresowo reszt
i i
a mod w = Ä…1Ò! a mod w = (Ä…1)
k s
okres kongruencji P(²,w)=k Ô! ² a" 1mod w & "s < k : ² mod w `" 1
k s
półokres kongruencji HP(²,w)=k Ô! ² a" -1mod w & "s < k : ² mod w `" -1
i k
reszty pot g baz ² wzgl dem modułów ² Ä…1 powtarzaj si okresowo
k k kj k j
² mod(² Ä…1) = m1Ò! ² mod(² Ä…1) = (m1)
kj+s k j s k
Ò! ² mod(² Ä…1) = (m1) ² mod(² Ä…1)
i 2
reszty pot g baz ² wzgl dem modułów ( ² Ä… ² +1) powtarzaj si okresowo:
2
² mod(² Ä… ² +1) = ²
2 2
² mod(² Ä… ² +1) = m² -1
3 2 2
² mod(² Ä… ² +1) = [² (m² -1)]mod(² Ä… ² +1) = Ä…1

© Janusz Biernat, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009 RNS 8
Systemy resztowe
Małe twierdzenie Fermata
TWIERDZENIE
Niech p b dzie liczb pierwsz . Je li p nie jest podzielnikiem liczby a, to
wtedy ap 1a"1(modp) za dla dowolnego a zachodzi apa"a(modp).
DOWÓD.
Skoro p nie dzieli a, to "1d"i`" jd"p 1: iÅ"a`"jÅ"amodp, wi c ka da liczba ci gu
1Å"a,2Å"a,3Å"a,& ,(p 1)Å"a nale y do innej klasy resztowej p 1.
, r=1,2,...,
p:r
A zatem [(1Å"a)(2Å"a)(3Å"a)& ((p 1)Å"a)]modp=(p 1)! modp, czyli
ap 1(p 1)! a"(p 1)!(modp)
Poniewa NWD(p,a)=1, wi c NWD(p,(ap 1 1)Å"(p 1)!)=p, (bowiem (p 1)!
nie dzieli si przez p). St d wynika, e
ap 1a"1(modp)
i poniewa p nie dzieli a, wi c aÅ"ap 1a"a(modp), a zatem
apa"a(modp)
Je li NWD(p,a)=p, to ostatnia zale no jest trywialna (amodp=0)

© Janusz Biernat, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009 RNS 9
Systemy resztowe
Funkcja Eulera Õ(N)
Õ
Õ
Õ
& co druga naturalna jest podzielna przez 2, co trzecia z pozostałych dzieli si
przez 3, co pi ta z niepodzielnych przez 2 lub 3 dzieli si przez 5, etc.
TWIERDZENIE
e1 e2 em
Je li podzielnikami liczby N s p1, p2, & , pm, czyli N = p1 p2 ...pm , pi" , to
liczb naturalnych mniejszych od N i wzgl dnie pierwszych z liczb N jest
i=m
-1
i
Õ(N) = , pi"
"( pi -1) pie
i=1
DOWÓD:
Je li pi jest podzielnikiem N, to w zbiorze {1,2,& ,N} jest N N(pi) 1 liczb
niepodzielnych przez pi. [N N(pi) 1] [N N(pi) 1] (pj) 1= N (1 (pi) 1)(1 (pj) 1)
spo ród nich nie jest podzielnych przez pj. (co pj-ta spo ród N i spo ród |pi)
Je li wi c pi i=1,2,...,m s liczbami pierwszymi, to w zbiorze {1,2,& ,N} jest
e1 e2 em -1 -1 - e1-1 e2 em
p1 p2 ...pm (1- p1 )(1- p2 )...(1- pm1) = p1 p2 -1...pm -1( p1 -1)( p2 -1)...( pm -1)
liczb niepodzielnych przez adn z nich.
WNIOSEK: Je li NWD(N,M)=1, to Õ(MN)=Õ(M)Õ(N).

© Janusz Biernat, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009 RNS 10
Systemy resztowe
Twierdzenie Eulera
TWIERDZENIE
Je li Õ(N) jest liczb liczb mniejszych od N i wzgl dnie pierwszych z N, to
aÕ ( N ) mod N =1
DOWÓD.
Je li N=p twierdzenie jest prawdziwe (Õ(p)=p 1) (maÅ‚e tw. Fermata).
pm-1 ( p-1)
Załó my, e twierdzenie jest prawdziwe dla N=pm, czyli a a"1mod pm .
pm-1 ( p-1) pm ( p-1)
St d wynika, e a = 1+ kpm oraz a = (1+ kpm)p = 1+ Kppm, zatem
pm ( p-1)
a a" 1mod pm+1. Twierdzenie jest wi c prawdziwe dla N=pÄ…, czyli
aÕ ( pm ) mod pm = 1
Je li wi c N = paqb... th , to aÕ ( paqb...th ) mod pa = (aÕ ( pa ))Õ (qb...th ) mod pa =1 oraz
...th
aÕ ( paqb...th ) mod qb = (aÕ (qb ))Õ ( pa ) mod qb =1 itd.. St d wynika teza twierdzenia:
...wh
aÕ ( paqb ) mod ( paqb...wh) = 1, czyli aÕ ( N ) mod N =1
WNIOSEK: aÕ ( N ) -1 a" a-1(mod N)

© Janusz Biernat, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009 RNS 11
Systemy resztowe
Chi skie twierdzenie o resztach  system RNS
m
Niech W={w1,w2,...,wm: "i`" j: NWD(wi,wj)=1} za W = wi Reprezentacja
"
i=1
X =)#x1,x2,& ,xm: xi=Xmodwi, wi"W*# ka dej liczby 0d"X*#
*#
*#
DOWÓD. Załó my, e "0d"X,Y "1d"id"m:wi|(Y-X), a poniewa W=NWW(w1,w2,& ,wm), to W|(Y -X).
Skoro jednak Y `" X, to Y Xe"W, co przeczy zało eniu, wi c Y =X
System resztowy RNS(w1,w2,& ,wm) (Residue Number System)
Reprezentacja X =)#x1modw1,x2modw2,& ,xmmodwm: wi"W*# w bazie W
" xi"{0,1,...,wi-1} dla kongruencji w zbiorze ,
" xi"{ ðÅ‚wi ûÅ‚, ,-1,0,1,...,ðÅ‚wi
/2 & /2-1ûÅ‚} dla kongruencji w zbiorze
WNIOSEK: W systemie RNS(w1,w2,& ,wm),
" ki" , 1d"id"m: |)#x1,x2,& ,xm*#|a"|)#x1Ä…k1w1,x2Ä…k2w2,& ,xmÄ…kmwm*#|modwi

© Janusz Biernat, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009 RNS 12
Systemy resztowe
Chi skie twierdzenie o resztach  konwersja odwrotna
CHI SKIE TWIERDZENIE O RESZTACH (CRT) (SUN-TZU, III W., QIN JIUSHAO, 1247)
Niech W={w1,w2,...,wn: "i`" j: NWD(wi,wj)=1}, W = w1w2...wn. Reprezentacja
)#x1,x2,& ,xn: xi=Xmodwi, wi"W*# ka dej liczby 0d"Xn
ëÅ‚
-1
X = |X| =
ìÅ‚ ÷Å‚
"u
(u
s mod ws )xs öÅ‚modW
s
íÅ‚ s=1 Å‚Å‚
-1 -1
gdzie u
s = Wws , za u
s mod ws  odwrotno u
s wzgl dem modułu ws.
DOWÓD (nieformalny szkic dowodu konwersji odwrotnej).
Ze wzgl du na zachowawczo kongruencji wobec dodawania mamy
)#x1,x2,& ,xn*# =x1Å")#1,0,& ,0,0*# +x2Å")#0,1,& ,0,0*# +& +xnÅ")#0,0,& ,0,1*# .
W systemie RNS(w1,w2,& ,wm) liczba ps o reprezentacji )#0,& ,0,1s,0,& ,0*# jest
podzielna przez ka de wi oprócz ws, jest wi c ps = k Å" u
s (liczby ps istniej , bo
ró nych reprezentacji jest dokładnie W). Poniewa jej reszta wzgl dem ws jest
-1 -1
równa 1, wi c k = u
s mod ws jest odwrotno ci u
s oraz ps = u
s(u
s mod ws).
)#x1,x2,& ,xn*# jest wi c reprezentacj liczby (x1p1+x2p2+& +xnpn) modW.

© Janusz Biernat, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009 RNS 13
Systemy resztowe
Wybór systemu resztowego
Dobór modułów  argumenty
" zakres reprezentowanych liczb  iloczyn wszystkich modułów
" łatwo i szybko wykonania działa modulo
" Å‚atwo konwersji i konwersji odwrotnej
moduÅ‚y ²k, ²k-1, ²k+1 dobrze speÅ‚niaj wymagania
(²k, ²k-1)=1, (²k, ²k+1)=1 oraz (²k-1, ²k+1)=1 (gdy ² parzyste)
w systemie dwójkowym
" je li (k,m)=1, to (2k 1,2m 1)=1 (liczby Mersenne a)
" przy pieszenie dodawania ~ proporcjonalne do log z liczby modułów
" im wi cej modułów tym trudniejsza konwersja odwrotna
opcje
W={2k+1,2k,2k-1}
W={2k+1,2k,2k-1,2k-3}
W={2k,2k-1,2i-1,& ,2s-1, s<...
© Janusz Biernat, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009 RNS 14
Systemy resztowe
Konwersja z systemu staÅ‚obazowego na system RNS(²k+1, ²k, ²k-1)
² + ² ² -
² + ² ² -
² + ² ² -
n-1
j
A² XRNS : xi = {
"(a mod wi )(² mod wi )}mod wi
j
j =0
reguÅ‚y podzielno ci Ò! reguÅ‚y konwersji z systemu naturalnego na RNS,
dla modułów o postaci ²k, ²k-1 i ²k+1.
n-1
s-1 k -1 s-1
i l ki
|A| = Ai ki ,
²
"a ² = "("a ² ) ² = "
i ik +l
i=0 i=0 l=0 i=0
k -1
gdzie Ai = aik +l l s warto ciami cyfr liczby A w systemie o bazie ²k.
²
"
l =0
k k k
Poniewa 0 d" Ai d" ² -1, zatem A mod ² = A0 mod ² oraz
s-1 s-1
k ki k k
A mod(² -1) = { Ai ² }mod(² -1) = { Ai }mod(² -1)
" "
i=0 i=0
s-1 s-1
k k i k i k
A mod(² +1) = { A ² }mod(² +1) = {
" "(-1) Ai }mod(² +1)
i
i=0 i=0

© Janusz Biernat, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009 RNS 15
Systemy resztowe
Konwersja z systemu resztowego na system stałobazowy (CRT)
pi=)#0,& ,1i,& ,0*#  jedynki resztowe (wagi), pi mod wi =1 i pi mod wj`"i = 0
Warto ci liczby XX = (x1p1 + x2 p2 + ...+ xn pn)modW ,
W celu wyznaczenia i-tej jedynki pi wystarczy wykona wi  1 oblicze . Mamy
|)#0,...,1i,...,0*#| = ku
i = k
"w = kwi-1W , 1d" k = u
i-1 mod wi d" wi -1,
s
i`"s
Obliczanie jedynek resztowych pi = u
i(u
i-1 mod wi) :
" rozwi zanie równania (u
i(u
i-1 mod wi ))mod wi =1, czyli
(u
i(u
i-1 mod wi ))mod wi = [(u
i mod wi)(u
i-1 mod wi )]mod wi
(... je li axmodw=-1, to a2xmodw=x 1modw)
" odwrócony algorytm Euklidesa  zapisujemy 1 jako sum wielokrotno ci
1 = x Å"(x-1 mod n) - k Å" n = x Å"(x-1 mod n) - k Å"[x Å" ndiv x + nmod x] = ...
" twierdzenie Eulera: aÕ ( N ) -1 a" a-1(mod N)

© Janusz Biernat, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009 RNS 16
Systemy resztowe
Konwersja z systemu resztowego na system stałobazowy
System resztowy RNS(a+1,a,a 1) (a=2p  musi by parzyste)
Mamy W=(a+1)Å"aÅ"(a 1). Obliczymy liczby u

j
u
3 = w1w2 = (a +1)a, u
3 mod w3 = 2Å"1 = 2
u
2 = w1w3 = (a +1)(a -1), u
2 mod w2 =1Å"(-1) = -1
u
1 = w2w3 = a(a -1), u
1 mod w1 = (-1)Å"(-2) = 2
oraz ich odwrotno ci multyplikatywne (u
i-1 = u
i-1 mod wi)
-1 -1 -1
u
3 u
3 mod w3 = 2 Å" u
3 mod(a -1) =1Ò! u
3 mod(a -1) = a / 2,
-1 -1 -1
u
2 u
2 mod w2 = -1Å" u
2 mod a =1Ò! u
2 mod a = -1
-1 -1 -1
u
1 u
1 mod w1 = 2 Å" u
1 mod(a +1) =1Ò! u
1 mod(a +1) = a / 2 +1
St d z3 = (a +1) Å" a Å" (a / 2), z2 = -(a +1) Å" (a -1), z1 = a Å" (a -1) Å" (a / 2 +1),
zatem warto ci liczby X o reprezentacji )#r3,r2,r1*# jest
X = (r3 z3+ r2 z2+ r1 z1) mod (a+1)Å"aÅ"(a 1).

© Janusz Biernat, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009 RNS 17
Systemy resztowe
Konwersja z systemu resztowego na system stałobazowy  przykłady (1)
a=2k
System resztowy (2k+1,2k,2k 1).
Mamy W=(2k+1)Å"2kÅ"(2k 1). Obliczymy liczby u

j
u
3 = w1w2 = (2k +1)2k , u
3 mod w3 = 2Å"1 = 2
u
2 = w1w3 = (2k +1)(2k -1), u
2 mod w2 =1Å"(-1) = -1
u
1 = w2w3 = 2k (2k -1), u
1 mod w1 = (-1)Å"(-2) = 2
oraz ich odwrotno ci multyplikatywne
-1 -1 -1
u
3 u
3 mod w3 = 2Å" u
3 mod(2k -1) = 1 Ò! u
3 mod(2k -1) = 2k -1,
-1 -1 -1
u
2 u
2 mod w2 = -1Å" u
2 mod 2k =1Ò! u
2 mod 2k = -1
-1 -1 -1
u
1 u
1 mod w1 = 2 Å" u
1 mod(2k +1) =1Ò! u
1 mod(2k +1) = 2k -1 +1
St d z3 = (2k +1) Å" 2k Å" 2k -1 = a, z2 = -(2k +1) Å"(2k -1), z1 = 2k Å" (2k -1) Å" (2k -1 +1),
zatem warto ci liczby X o reprezentacji )#r3,r2,r1*#
jest X = (r3 z3+ r2 z2+ r1 z1) mod (22k 1)Å"2k.

© Janusz Biernat, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009 RNS 18
Systemy resztowe
Konwersja z systemu resztowego na system stałobazowy  przykłady (2)
W systemie resztowym (7,3,2) mamy X(7,3,2) = )#3,2,1*#. Wyznaczmy X10.
Mamy W=2Å"3Å"7=42. Obliczymy liczby u

j
u
3 = W / w3 = 6, u
3 mod w3 = -1 a" 6mod7
u
2 = W / w2 = 14, u
2 mod w2 = -1 a" 2mod3
u
1 = W / w1 = 21, u
1 mod w1 =1
oraz ich odwrotno ci multyplikatywne
-1 -1 -1
u
3 u
3 mod w3 = -1Å" u
3 mod w3 =1Ò! u
3 mod w3 = -1,
-1 -1 -1
u
2 u
2 mod w2 = -1Å" u
2 mod w2 =1Ò! u
2 mod w2 = -1
-1 -1 -1
u
1 u
1 mod w1 = Ä…1Å" u
1 mod w1 =1Ò! u
1 mod w1 = Ä…1
St d z3= 6a"36mod42, z2= 14a"28mod42, z3= 21a"21mod42,
zatem X = (( 1)Å"3Å"6 +( 1)Å"2Å"14 + 1Å"1Å"21) mod 42 =  25 mod 42 = 17.
Rzeczywi cie X(7,3,2) = )#17 mod 7, 17 mod 3, 17 mod 2*# = )#3,2,1*#.

© Janusz Biernat, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009 RNS 19
Systemy resztowe
Obliczanie odwrotno ci multyplikatywnych  (1)
Odwrócony algorytm Euklidesa
1 = x Å"(x-1 mod n) - k Å" n = x Å"(x-1 mod n) - k Å"[x Å" ndiv x + nmod x] = ...
= ... = p Å"(AÅ" x-1 mod n - B Å" n) + (C Å" x-1 mod n - D Å" n) = p Å"0 +1
Jedynki w systemie RNS(7,3,2)  mamy W=2Å"3Å"7=42. Obliczymy liczby u

j
u
3 = W / w3 = 6, u
3 mod w3 = -1 a" 6mod7
u
2 = W / w2 = 14, u
2 mod w2 = -1 a" 2mod3
u
1 = W / w1 = 21, u
1 mod w1 =1
oraz ich odwrotno ci multyplikatywne (u
i-1 = u
i-1 mod wi )
- - - -
1 = u
3 Å" u
31 - t Å" w3 = 6u
31 - 7t = 6u
31 - (1Å"6 +1) Å"t = 6 Å" (u
31 - t) - t ,
- -
zatem u
31 - t = 0 oraz t = -1, czyli u
31 = -1
- - - - -
1 = u
2 Å" u
21 - t Å" w2 =14u
21 - 3t = (3Å"5 -1)Å" u
21 - 3t = 3Å"(5Å" u
21 - t) - u
21,
-
zatem u
21 = -1 oraz t = -5
-1 -1 -1 -1 -1
1 = u
1 Å" u
1 - t Å" w1 = 21u
1 - 2t = (10Å" 2 +1)Å" u
1 - 2t = 2Å"(10Å" u
1 - t) + u
1 ,
-1
zatem u
1 =1 oraz t =10

© Janusz Biernat, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009 RNS 20
Systemy resztowe
Obliczanie odwrotno ci multyplikatywnych  (2)
Jedynki w systemie RNS(7,3,2)  twierdzenie Eulera
i i
1 = (u
i)w -1 mod wi = (u
i-1 mod wi)Å"(u
i)w mod wi
Mamy W=2Å"3Å"7=42. Obliczymy liczby u

j
u
3 = W / w3 = 6, u
3 mod w3 = -1 a" 6mod7
u
2 = W / w2 = 14, u
2 mod w2 = -1 a" 2mod3
u
1 = W / w1 = 21, u
1 mod w1 =1
oraz ich odwrotno ci multyplikatywne (u
i-1 = u
i-1 mod wi )
1 = (u
3)7-1 mod7 a" (6-1 mod7)(67 mod7) = -6-1 mod7,
-
zatem u
31 = 6-1 mod7 = -1
1 = (u
2)3-1 mod3 a" (14-1 mod3)(143 mod3) = -14-1 mod3,
-
zatem u
21 =14-1 mod3 = -1
1 = (u
1)2-1 mod 2 a" (21-1 mod 2)(212 mod 2) = 21-1 mod 2,
-1
zatem u
1 = 21-1 mod 2 =1
St d z3= 6a"36mod42, z2= 14a"28mod42, z3= 21a"21mod42,

© Janusz Biernat, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009 RNS 21
Systemy resztowe
Wyznaczanie reprezentacji resztowych
1. Z twierdzenia Fermata lub Eulera  reszty pot g  redukcja pot gi modÕ(p)
axmodN=(aÕ (p))[ x div Õ (p) ]ax mod Õ (p)modN=ax mod Õ (p) modN
Ponadto
2
i
0 1 2
aX mod p = a"x 2i mod p = [(a mod p)x (a2 mod p)x (a2 mod p)x ...]mod p
2. Poniewa dla liczby naturalnej a>3
a modaÄ…1=-(Ä…1) Ò! ak modaÄ…1=[-(Ä…1)]k
wi c dla ka dej liczby naturalnej danej w reprezentacji pozycyjnej o podstawie
² reszty mod²kÄ…1 mo na obliczy jako sumy lub ró nice liczb k-cyfrowych,
utworzonych przez cyfry na pozycjach jk,jk+1,& ,jk+k 1 (j=0,1,2,& )
n-1 îÅ‚n / k Å‚Å‚ -1
k
ëÅ‚ öÅ‚
ëÅ‚
i k i kj k
(
ìÅ‚ ÷Å‚
"x ² öÅ‚mod(² Ä…1) = ìÅ‚ " "x ² )² ÷Å‚
i kj+i
ìÅ‚ ÷Å‚mod(² Ä…1) =
íÅ‚ i=0 Å‚Å‚ j=0 i=0
íÅ‚ Å‚Å‚
k
îÅ‚n / k Å‚Å‚ -1
ëÅ‚ öÅ‚
i j k
ìÅ‚
= (
" "x ² )(Ä…1) ÷Å‚
kj+i
ìÅ‚ ÷Å‚mod(² Ä…1)
j=0 i=0
íÅ‚ Å‚Å‚

© Janusz Biernat, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009 RNS 22
Systemy resztowe*
System kwadratowo-resztowy QRNS*
 arytmetyka liczb zespolonych (obliczanie transformaty Fouriera).
reprezentacja resztowa jednostki urojonej i = -1.
q2 mod w = -1, Ò! q mod w = -1.
problem: znalezienie zbioru modułów, dla których jest rozwi zanie równania
2
q mod w = -1.
DEFINICJA
Liczb r, pierwsz wzgl dem w" N i tak e równanie x2 mod w = r ma
rozwi zanie, nazywa si reszt kwadratow (quadratic residue) wzgl dem w.
Je eli natomiast równanie x2 mod w = r nie ma rozwi zania, to r nazywa si
nie-reszt kwadratow (quadratic nonresidue) wzgl dem w.

© Janusz Biernat, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009 RNS 1*
Systemy resztowe*
Reszty kwadratowe*
Poniewa jest dokładnie (w-1) reszt niezerowych modulo w, a ka de równanie
x2 mod w = r ma albo dwa rozwi zania nieprzystaj ce x oraz -x (lub w-x, bo
x2 mod w = (w - x)2 mod w), albo nie ma rozwi zania, wi c przy nieparzystym
w istnieje dokładnie (w-1)/2 reszt oraz (w-1)/2 nie-reszt kwadratowych.
Reszty kwadratowe wzgl dem w = 13 wyznaczymy rozwi zuj c równanie
x2 mod 13 = r metod kolejnych prób dla x = 1, 2,..., 6 (.x2 a" (w x)2 mod w)
Znajdujemy odpowiednio: 12 a" 1 mod 13, 22 a" 4 mod 13, 32 a" -4 mod 13,
42 a" 3 mod 13, 52 a" -1 mod 13, 62 a" -3 mod 13. Zatem resztami kwadratowymi
wzgl dem 13 s (w arytmetyce uzupełnieniowej): -4, -3, -1, 1, 3, 4.

© Janusz Biernat, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009 RNS 2*
Systemy resztowe*
Chi skie twierdzenie o resztach  konwersja odwrotna*
-1
Niech W={w1,w2,...,wn: "i`"j: (wi,wj)=1}, W = w1w2...wn oraz u
s = Wws .
Je li 0d"|X |unikatowa, przy tym
n
ëÅ‚
-1
X = |X| =
ìÅ‚ ÷Å‚
"u
(u
s mod ws )xs öÅ‚modW
s
íÅ‚ s=1 Å‚Å‚
-1
gdzie u
s mod ws  odwrotno multyplikatywna u
s wzgl dem modułu ws.
DO W Ó D (formalny).
-1
Niech ps = u
s mod ws. Poniewa xs = X mod ws oraz W = u
s ws , zatem
-1
(u
s(u
s mod ws)xs)modW = (u
s ps(X mod ws))modW =
= (u
s ps(X - ws / ws ))modW = (X u
s ps ) modW ,
ðÅ‚X ûÅ‚
i na podstawie zachowawczo ci kongruencji
n n n
ëÅ‚
(i) X u
s ps öÅ‚modW = (X modW )ëÅ‚
ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚
" "u
ps öÅ‚modW = XëÅ‚"u
ps öÅ‚modW .
s s
íÅ‚ s=1 Å‚Å‚ íÅ‚ s=1 Å‚Å‚ íÅ‚ s=1 Å‚Å‚

© Janusz Biernat, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009 RNS 3*
Systemy resztowe*
Aby dowie prawdziwo ci tezy wystarczy wi c wykaza , e
n
( u
s ps ) modW = 1.
"
s=1
Poniewa z udowodnionego wcze niej lematu wynika, e
NWD(x,y)=1 '" amody=d '" amodx=d Ò! amodxy=d,
za W = w1w2...wn-1wn jest iloczynem liczb wzgl dnie pierwszych, wi c
wystarczy wykaza prawdziwo poprzednika implikacji
n n
(ii) "wi : (
"u
ps)mod wi = 1Ò! ("u
ps)modW = 1.
s s
s=1 s=1
n
1
Ale u
s =
"w Ò! "i `" s : wi / u
s , zatem
ws i=1 i
n
(iii) (
"u
ps)mod wi = (u
i pi )mod wi = (u
i(u
i-1 mod wi))mod wi = 1.
s
s=1
St d wynika prawdziwo nast pnika implikacji (ii), co dowodzi tezy.

© Janusz Biernat, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009 RNS 4*