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 N"Q=(M"P)+(Å›"b+P"a+a"b)w
Iloraz całkowity Xdivw (w"
"X" : X-Xmodw=wÅ"Xdivw
z
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa dziernika 2006 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 1modw liczby x modulo w
a=x 1modw Ô! ax modw=1
! (je li x i w maj wspólny podzielnik p`" 1, to zÅ"xmodw=1 nie ma rozwi zania)
z
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa dziernika 2006 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 m
1. 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.
z
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa dziernika 2006 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)
z
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa dziernika 2006 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)
[X1, X2,& , Xm]=W" Ô! "i: Xi|W '" Ź"Z" : (Zz
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa dziernika 2006 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
ëÅ‚
i i
ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚
"x ² öÅ‚mod (² +1) = ëÅ‚"(-1) xi öÅ‚mod (² +1)
i
íÅ‚ 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
z
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa dziernika 2006 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-1x ² öÅ‚mod (² -1) = ìÅ‚ îÅ‚n / k Å‚Å‚-1 ÷Å‚mod (² -1)
i k k
Xi ÷Å‚
ìÅ‚ ÷Å‚
" "
i
ìÅ‚
íÅ‚i=0 Å‚Å‚ i=0
íÅ‚ Å‚Å‚
ëÅ‚ öÅ‚
ëÅ‚n-1x ² öÅ‚mod (² +1) = ìÅ‚ îÅ‚n / k Å‚Å‚-1(-1)i Xi ÷Å‚mod (² +1)
i k k
ìÅ‚ ÷Å‚
" "
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
z
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa dziernika 2006 RNS 7
Systemy resztowe
Okresowo reszt
i i
a mod w = Ä…1Ò! a mod w = (Ä…1)
k s
okres kongruencji k ² a" 1mod w & "s < k : ² mod w `" 1
k s
półokres kongruencji 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
z
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa dziernika 2006 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)
z
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa dziernika 2006 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 -1) pie , pi"
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).
z
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa dziernika 2006 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
aÕ ( paqb...th ) mod qb = (aÕ (qb ))Õ ( pa ...th ) mod qb =1 itd.. St d wynika teza twierdzenia:
aÕ ( paqb ...wh ) mod ( paqb...wh) = 1, czyli aÕ ( N ) mod N =1
WNIOSEK: aÕ ( N ) -1 a" a-1(mod N)
z
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa dziernika 2006 RNS 11
Systemy resztowe
Chi skie twierdzenie o resztach system RNS
m
Niech W={w1,w2,...,wm: "i`" j: NWP(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
z
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa dziernika 2006 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: NWP(wi,wj)=1}, W = w1w2...wn. Reprezentacja
)#x1,x2,& ,xn: xi=Xmodwi, wi"W*# ka dej liczby 0d"Xn
ëÅ‚
-1
X = |X| =
ìÅ‚ ÷Å‚
"u (us mod ws )xs öÅ‚modW
s
íÅ‚ s=1 Å‚Å‚
-1 -1
gdzie us = Wws , za us mod ws odwrotno us 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 Å" us (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 = us mod ws jest odwrotno ci us oraz ps = us(us mod ws).
)#x1,x2,& ,xn*# jest wi c reprezentacj liczby (x1p1+x2p2+& +xnpn) modW.
z
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa dziernika 2006 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<...z
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa dziernika 2006 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 ki k i k
A mod(² +1) = { A ² }mod(² +1) = {
" "(-1) Ai }mod(² +1)
i
i=0 i=0
z
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa dziernika 2006 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*#| = kui = k
"w = kwi-1W , 1d" k = ui-1 mod wi d" wi -1,
s
i`"s
Obliczanie jedynek resztowych pi = ui(ui-1 mod wi) :
" rozwi zanie równania (ui(ui-1 mod wi ))mod wi =1, czyli
(ui(ui-1 mod wi ))mod wi = [(ui mod wi)(ui-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)
z
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa dziernika 2006 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
u3 = w1w2 = (a +1)a, u3 mod w3 = 2Å"1 = 2
u2 = w1w3 = (a +1)(a -1), u2 mod w2 =1Å"(-1) = -1
u1 = w2w3 = a(a -1), u1 mod w1 = (-1)Å"(-2) = 2
oraz ich odwrotno ci multyplikatywne (ui-1 = ui-1 mod wi)
-1 -1 -1
u3 u3 mod w3 = 2 Å" u3 mod(a -1) =1Ò! u3 mod(a -1) = a / 2,
-1 -1 -1
u2 u2 mod w2 = -1Å" u2 mod a =1Ò! u2 mod a = -1
-1 -1 -1
u1 u1 mod w1 = 2 Å" u1 mod(a +1) =1Ò! u1 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).
z
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa dziernika 2006 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
u3 = w1w2 = (2k +1)2k , u3 mod w3 = 2Å"1 = 2
u2 = w1w3 = (2k +1)(2k -1), u2 mod w2 =1Å"(-1) = -1
u1 = w2w3 = 2k (2k -1), u1 mod w1 = (-1)Å"(-2) = 2
oraz ich odwrotno ci multyplikatywne
-1 -1 -1
u3 u3 mod w3 = 2Å" u3 mod(2k -1) = 1 Ò! u3 mod(2k -1) = 2k -1,
-1 -1 -1
u2 u2 mod w2 = -1Å" u2 mod 2k =1Ò! u2 mod 2k = -1
-1 -1 -1
u1 u1 mod w1 = 2 Å" u1 mod(2k +1) =1Ò! u1 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.
z
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa dziernika 2006 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
u3 = W / w3 = 6, u3 mod w3 = -1 a" 6mod7
u2 = W / w2 = 14, u2 mod w2 = -1 a" 2mod3
u1 = W / w1 = 21, u1 mod w1 =1
oraz ich odwrotno ci multyplikatywne
-1 -1 -1
u3 u3 mod w3 = -1Å" u3 mod w3 =1Ò! u3 mod w3 = -1,
-1 -1 -1
u2 u2 mod w2 = -1Å" u2 mod w2 =1Ò! u2 mod w2 = -1
-1 -1 -1
u1 u1 mod w1 = Ä…1Å" u1 mod w1 =1Ò! u1 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*#.
z
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa dziernika 2006 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
u3 = W / w3 = 6, u3 mod w3 = -1 a" 6mod7
u2 = W / w2 = 14, u2 mod w2 = -1 a" 2mod3
u1 = W / w1 = 21, u1 mod w1 =1
oraz ich odwrotno ci multyplikatywne (ui-1 = ui-1 mod wi )
- - - -
1 = u3 Å" u31 - t Å" w3 = 6u31 - 7t = 6u31 - (1Å"6 +1) Å"t = 6 Å" (u31 - t) - t ,
- -
zatem u31 - t = 0 oraz t = -1, czyli u31 = -1
- - - - -
1 = u2 Å" u21 - t Å" w2 =14u21 - 3t = (3Å"5 -1)Å" u21 - 3t = 3Å"(5Å" u21 - t) - u21,
-
zatem u21 = -1 oraz t = -5
-1 -1 -1 -1 -1
1 = u1 Å" u1 - t Å" w1 = 21u1 - 2t = (10Å" 2 +1)Å" u1 - 2t = 2Å"(10Å" u1 - t) + u1 ,
-1
zatem u1 =1 oraz t =10
z
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa dziernika 2006 RNS 20
Systemy resztowe
Obliczanie odwrotno ci multyplikatywnych (2)
Jedynki w systemie RNS(7,3,2) twierdzenie Eulera
i i
1 = (ui)w -1 mod wi = (ui-1 mod wi)Å"(ui)w mod wi
Mamy W=2Å"3Å"7=42. Obliczymy liczby u
j
u3 = W / w3 = 6, u3 mod w3 = -1 a" 6mod7
u2 = W / w2 = 14, u2 mod w2 = -1 a" 2mod3
u1 = W / w1 = 21, u1 mod w1 =1
oraz ich odwrotno ci multyplikatywne (ui-1 = ui-1 mod wi )
1 = (u3)7-1 mod7 a" (6-1 mod7)(67 mod7) = -6-1 mod7,
-
zatem u31 = 6-1 mod7 = -1
1 = (u2)3-1 mod3 a" (14-1 mod3)(143 mod3) = -14-1 mod3,
-
zatem u21 =14-1 mod3 = -1
1 = (u1)2-1 mod 2 a" (21-1 mod 2)(212 mod 2) = 21-1 mod 2,
-1
zatem u1 = 21-1 mod 2 =1
St d z3= 6a"36mod42, z2= 14a"28mod42, z3= 21a"21mod42,
z
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa dziernika 2006 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
íÅ‚ Å‚Å‚
z
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa dziernika 2006 RNS 22
Wyszukiwarka
Podobne podstrony:
2009 5 systemy resztowe
2004 systemy resztowe
systemy bukmacherskie 2006 darmowy fragment
2006 09 Wielozadaniowość w systemach operacyjnych [Inzynieria Oprogramowania]
2006 04 11 Uchwała ZG OSP system szkoleniaid 456
systemy bukmacherskie 2006 (zaklady sportowe)
Systemy ochrony przeciwprzepięciowej (2006)
2006 08 Zarządzanie pamięcią w systemach operacyjnych [Inzynieria Oprogramowania]
2006 02 Menus and Choices Creating a Multimedia Center with Mpeg Menu System V2
2006 10 Skrypty powłoki w systemie Linux [Poczatkujacy]
2006 07 JÄ…dro systemu operacyjnego [Inzynieria Oprogramowania]
wylaczenie aktualizacji systemu XP
EV (Electric Vehicle) and Hybrid Drive Systems
więcej podobnych podstron