Systemy resztowe
Kongruencje
Liczby kongruentne (przystające) modulo w"N (w moduł przystawania)
" w zbiorze liczb naturalnych N
"(N,M"N): Na"Mmodw Ô!"k"N: N-M=kw (" M-N=kw
" w zbiorze liczb całkowitych Z
"(N,M"Z): Na"Mmodw Ô!"k"Z: N-M=kw
Kongruencja relacja równowa\ności:
" zwrotna (reflexive): Na"Nmodw,
" symetryczna (symmetric): Na"MmodwÔ!Ma"Nmodw,
" przechodnia (transitive): Na"Mmodw&Ma"PmodwÒ!Na"Pmodw.
" zachowawcza (indifferent) wobec dodawania, odejmowania i mno enia
Na"Mmodw '" Qa"Pmodw Ò! (NÄ…Q)a"(MÄ…P)modw,
Na"Mmodw '" Qa"Pmodw Ò! NÅ"Qa"MÅ"Pmodw.
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004 RNS 1
Systemy resztowe
Klasy kongruencji
Klasy kongruencji (równowa\ności względem relacji przystawania)
" w zbiorze liczb naturalnych N
w-1
Nw:r={N"N:Na"rmodw;0d"r
UN = N
w:r
r =0
" w zbiorze liczb całkowitych Z
w-1
Zw:r={Z"Z:Za"rmodw; ðÅ‚-w/2ûÅ‚ d"r<ðÅ‚w/2ûÅ‚},
UZ = Z
w:r
r =0
r reszta z dzielenia (residue) liczby całkowitej (naturalnej) przez moduł w
Zauwa my, e
"w" N : Nw:r ‚" Zw:r (" Nw:r ‚" Zw:r -w
" N7:5={5,12,19,26,& } ‚" Z7: 2={& , 9, 2,5,12,19,26,& }
" N7:1={1,8,15,22,& } ‚" Z7:1={& , 13, 6,1,8,15,22,& }
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004 RNS 2
Systemy resztowe
Podzielniki i liczby pierwsze
Podzielnik liczby w|N Ô! Nmodw=0, w"N
Największy wspólny (po)dzielnik NWD (greatest common divisor, GCD)
(X,Y )=a"N Ô! (a|X '"a|Y ) '" Ź"b"N: (b>a)'"(b|X '"b|Y )
Liczby względnie pierwsze (relatively prime): (X,Y )=1.
Algorytm Euklidesa
Je li X>Y oraz w|X i w|Y, to w|(X kY) wi c w|(XmodY).
St d wynika, e w|(Y mod(XmodY)) itd., dopóki reszta nie jest równa 0.
Wtedy ostatni podzielnik jest NWD(X,Y).
Xdivw iloraz całkowity X/w
Xmodw reszta z dzielenia całkowitego X/w
X=wÅ"Xdivw+Xmodw
(Xa"Xmodw) modw
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004 RNS 3
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"N Ô! "i: Xi|W '" Ź"Z"N: (Z© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004 RNS 4
Systemy resztowe
Funkcja Eulera (Õ(N))
Õ
Õ
Õ
liczba liczb naturalnych intuicja:
co druga liczba naturalna jest podzielna przez 2,
spo ród niepodzielnych przez 2 co trzecia jest podzielna przez 3,
spo ród niepodzielnych przez 2 i 3 co pi ta jest podzielna przez 5 etc.,
TWIERDZENIE
e1 e2 em
Je li podzielnikami N s liczby p1, p2, & , pm, czyli N = p1 p2 ...pm , pi " ,
p1 -1 p2 -1 pm -1
to Õ(N) = N ... , pi "
p1 p2 pm
DOWÓD:
(przez indukcjÄ™ lub wyprowadzenie na podstawie wy\ej podanego wnioskowania intuicyjnego)
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004 RNS 5
Systemy resztowe
Małe twierdzenie Fermata
Niech p będzie liczbą pierwszą zaś a nie jest podzielna przez p ((p,a)=1).
Wówczas ap 1a"1modp oraz apa"amodp.
DOWÓD. Skoro p nie dzieli a, to ka da liczba ci gu 1Å"a,2Å"a,3Å"a,& ,(p 1)Å"a
nale y do innej klasy resztowej Zp:r ("1d"i`" jd"p 1: iÅ"a`" jÅ"amodp). A zatem
(1Å"a)(2Å"a)(3Å"a)& ((p 1)Å"a)=ap 1(p 1)! a"(p 1)! modp
Poniewa ((p 1)!,p)=1 oraz (p,a)=1, wi c ((ap 1 1)Å"(p 1)!,p)=p, a zatem
ap 1a"1modp oraz aÅ"ap 1a"amodp.
Wniosek: ap 2a" a 1modp
Twierdzenie Eulera
JeÅ›li Õ(N) jest liczb liczb mniejszych od N i wzgl dnie pierwszych z N, to
aÕ ( N ) mod N =1
oraz
aÕ ( N )-1 a" a-1 mod N
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004 RNS 6
Systemy resztowe
Chi skie twierdzenie o resztach
m
Niech W={w1,w2,...,wm: "i`" j: (wi,wj)=1}oraz W = wi . Dla 0d"|X |"
i=1
reprezentacja X =)#x1,x2,& ,xm: xi=|X |modwi, wi"W*# jest unikatowa.
*#
*#
*#
DOWÓD. Załó my, e "0d"Y Zatem "1d"id"m:wi|(Y -Z), a poniewa W=[[w1,w2,& ,wm]], to W|(Y -Z).
Skoro jednak Y `" Z, to Y Ze"W, co przeczy zało eniu, wi c Y =Z
System RNS(w1,w2,& ,wm)
Reprezentacja X =)#x1modw1,x2modw2,& ,xmmodwm: wi"W*# w bazie W
" xi"{0,1,...,wi-1} dla kongruencji w zbiorze N,
" xi"{ ðÅ‚wi ûÅ‚, ,-1,0,1,...,ðÅ‚wi
/2 & /2-1ûÅ‚} dla kongruencji w zbiorze Z
WNIOSEK: W systemie RNS(w1,w2,& ,wm),
" ki"N, 1d"id"m: |)#x1,x2,& ,xm*#|a"|)#x1Ä…k1w1,x2Ä…k2w2,& ,xmÄ…kmwm*#|modwi
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004 RNS 7
Systemy resztowe
Inne wła ciwo ci reprezentacji resztowych
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 (pro ciej)
Je li Xmodw1=q oraz Xmodw2=q, to (X q)modw1=0 oraz (X q)modw2=0
zatem X q= k1w1 X q= k2w2 sk d wynika, e X q= k w1w2, zatem
(X q)mod(w1w2)=0, wi c Xmod(w1w2)=q.
WAASNOŚĆ:
Je li a|X oraz a|w, to (aX)mod(aw)=a(Xmodw)
(aX)mod(aw)=aX-awðÅ‚aX/awûÅ‚=a(X-wðÅ‚X/wûÅ‚)=a(X modw)
Odwrotność multyplikatywna (multiplicative inverse) w systemie RNS
z = x-1 mod w Ô! zx mod w = 1.
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004 RNS 8
Systemy resztowe
Podzielno liczb (1)
k -1 k -1
ëÅ‚
i i
ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚
"x ² öÅ‚mod w = ëÅ‚"(x mod w)(² mod w)öÅ‚mod w,
i 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) = ëÅ‚ öÅ‚mod (² -1)
i
xi²
ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚
" "x
i
íÅ‚ 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
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004 RNS 9
Systemy resztowe
Podzielno liczb (2)
n-1
îÅ‚n / k Å‚Å‚-1 k -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 îÅ‚n / k Å‚Å‚-1
ëÅ‚ öÅ‚
ëÅ‚
i k k
Xi ÷Å‚mod (² -1)
ìÅ‚ ÷Å‚
"x ² öÅ‚mod (² -1) = ìÅ‚ "
i
ìÅ‚ ÷Å‚
íÅ‚ i=0 Å‚Å‚ i=0
íÅ‚ Å‚Å‚
n-1 îÅ‚n / k Å‚Å‚-1
ëÅ‚ öÅ‚
ëÅ‚
i k k
(-1)i Xi ÷Å‚mod (² +1)
ìÅ‚ ÷Å‚
"x ² öÅ‚mod (² +1) = ìÅ‚ "
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, Systemy resztowe'04, 26 grudnia 2004 RNS 10
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
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004 RNS 11
Systemy resztowe
Chi skie twierdzenie o resztach konwersja odwrotna
-1
Niech W={w1,w2,...,wn: "i`" j: (wi,wj)=1}, W = w1w2...wn oraz us = Wws .
Jeśli 0d"|X |unikatowa, przy tym
n
ëÅ‚
-1
X = |X| = (us mod ws )xs öÅ‚modW
ìÅ‚ ÷Å‚
"u
s
íÅ‚ s=1 Å‚Å‚
-1
gdzie us mod ws odwrotność multyplikatywna us względem modułu ws .
DOWÓD (nieformalny).
-1
Je li us mod ws jest odwrotno ci multyplikatywn us, to )#0,& ,0,1s,0,& ,0*#
-1
jest reprezentacj resztow us(us mod ws ) w systemie RNS(w1,w2,& ,wm), bo
liczba ta jest podzielna przez wszystkie wi z wyj tkiem ws.
Poniewa reszta z sumy jest równa sumie reszt, wi c
X =)#x1,x2,& ,xn*# =x1Å")#1,0,& ,0,0*# +x2Å")#0,1,& ,0,0*# +& +xnÅ")#0,0,& ,0,1*#
jest reprezentacj resztow liczby X o warto ci danej wyra eniem w nawiasie
oraz ka dej liczby przystaj cej do niej modulo W.
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004 RNS 12
Systemy resztowe
Chi skie twierdzenie o resztach konwersja odwrotna
-1
Niech W={w1,w2,...,wn: "i`" j: (wi,wj)=1}, W = w1w2...wn oraz us = Wws .
Jeśli 0d"|X |unikatowa, przy tym
n
ëÅ‚
-1
X = |X| = (us mod ws )xs öÅ‚modW
ìÅ‚ ÷Å‚
"u
s
íÅ‚ s=1 Å‚Å‚
-1
gdzie us mod ws odwrotność multyplikatywna us względem modułu ws .
DO W Ó D.
-1
Niech ps = us mod ws. Poniewa xs = X mod ws oraz W = us ws , zatem
-1
(us (us mod ws )xs)modW = (us ps (X mod ws))modW =
= (us ps(X - ws / ws ))modW = (X us ps ) modW ,
ðÅ‚X ûÅ‚
i na podstawie zachowawczo ci kongruencji
n n n
ëÅ‚
(i) X us ps öÅ‚modW = (X modW )ëÅ‚ s ps öÅ‚modW = XëÅ‚ s ps öÅ‚modW .
ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚
" "u "u
íÅ‚ s=1 Å‚Å‚ íÅ‚ s=1 Å‚Å‚ íÅ‚ s=1 Å‚Å‚
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004 RNS 13
Systemy resztowe
Aby dowie prawdziwo ci tezy wystarczy wi c wykaza , e
n
( us ps ) modW = 1.
"
s=1
Poniewa z udowodnionego wcze niej lematu (2.49) wynika, e
(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 : ( ps )mod wi = 1Ò! ( ps)modW = 1.
"u "u
s s
s=1 s=1
n
1
Ale us =
"w Ò! "i `" s : wi / us , zatem
ws i=1 i
n
(iii) ( ps )mod wi = (ui pi )mod wi = (ui (ui-1 mod wi ))mod wi = 1.
"u
s
s=1
St d wynika prawdziwo nast pnika implikacji (ii), co dowodzi tezy.
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004 RNS 14
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, Systemy resztowe'04, 26 grudnia 2004 RNS 15
Systemy resztowe
Konwersja z systemu staÅ‚obazowego na system RNS(²k+1, ²k, ²k-1)
² + ² ² -
² + ² ² -
² + ² ² -
n-1
j
A² XRNS : xi = { mod wi )(² mod wi )}mod wi
"(a
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, Systemy resztowe'04, 26 grudnia 2004 RNS 16
Systemy resztowe
Konwersja z systemu resztowego na system stałobazowy (CRT)
zi=)#0,& ,1i,& ,0*# jedynki resztowe (wagi), zi mod wi = 1 i zi mod w = 0
j`"i
Warto ci liczby Xn
X = ( xi zi ) modW ,
"
i=1
W celu wyznaczenia i-tej jedynki zi wystarczy wykona wi 1 oblicze . Mamy
|)#0,...,1i,...,0*#| = kui = k = kwi-1W , 1 d" k = ui-1 mod wi d" wi -1,
"w
s
i`"s
Obliczanie jedynek resztowych zi = ui (ui-1 mod wi ):
" rozwi zanie równania (ui (ui-1 mod wi ))mod wi =1
(ui (ui-1 mod wi ))mod wi = [(ui mod wi )(ui-1 mod wi )]mod wi
" 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] = ...
" małe twierdzenie Fermata ((p,a)=1 ap 1a"1modp
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004 RNS 17
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).
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004 RNS 18
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.
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004 RNS 19
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*#.
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004 RNS 20
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
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004 RNS 21
Systemy resztowe
Obliczanie odwrotno ci multyplikatywnych (2)
Jedynki w systemie RNS(7,3,2) małe twierdzenie Fermata
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,
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004 RNS 22
Systemy resztowe
System kwadratowo-resztowy QRNS
arytmetyka liczb zespolonych (obliczanie transformaty Fouriera).
reprezentacja resztowa jednostki urojonej i = -1.
2
q 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, Systemy resztowe'04, 26 grudnia 2004 RNS 23
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, Systemy resztowe'04, 26 grudnia 2004 RNS 24
Wyszukiwarka
Podobne podstrony:
2009 5 systemy resztowe
2006 systemy resztowe
2004 charakterystyka systemow liczbowych
2004 03 Analiza logów systemowych [Administracja]
Quick Study Chart Circulatory System (BarCharts Inc, 2004) WW
2004 01 Loop AES – szyfrowane systemy plików [Bezpieczenstwo]
2004 03 CVS – system zarządzania wersjami [Programowanie]
wylaczenie aktualizacji systemu XP
EV (Electric Vehicle) and Hybrid Drive Systems
system ósemkowy
ANALIZA KOMPUTEROWA SYSTEMÓW POMIAROWYCH — MSE
więcej podobnych podstron