Systemy resztowe
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004
RNS–1
Kongruencje
Liczby kongruentne (przystaj
ą
ce) modulo w
∈
N (w – moduł przystawania)
•
w zbiorze liczb naturalnych N
∀
(N,M
∈
N): N
≡
M mod w
⇔∃
k
∈
N: N
−
M
=
kw
∨
M
−
N
=
kw
•
w zbiorze liczb całkowitych Z
∀
(N,M
∈
Z): N
≡
M mod w
⇔∃
k
∈
Z: N
−
M
=
kw
Kongruencja – relacja równowa
Ŝ
no
ś
ci:
•
zwrotna (reflexive): N
≡
N mod w,
•
symetryczna (symmetric): N
≡
M mod w
⇔
M
≡
N mod w,
•
przechodnia (transitive): N
≡
M mod w & M
≡
P mod w ⇒ N
≡
P mod w.
•
zachowawcza (indifferent) wobec dodawania, odejmowania i mno enia
N
≡
M mod w
∧
Q
≡
P mod w ⇒
(N
±
Q)
≡
(M
±
P) mod w,
N
≡
M mod w
∧
Q
≡
P mod w ⇒
N
⋅
Q
≡
M
⋅
P mod w.
Systemy resztowe
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004
RNS–2
Klasy kongruencji
Klasy kongruencji (równowa
Ŝ
no
ś
ci wzgl
ę
dem relacji przystawania)
•
w zbiorze liczb naturalnych N
N
w:r
=
{ N
∈
N: N
≡
r mod w ; 0
≤
r < w },
N
N
=
−
=
U
1
0
:
w
r
r
w
•
w zbiorze liczb całkowitych
Z
Z
w:r
=
{ Z
∈
Z
: Z
≡
r mod w ;
−
w /2
≤
r < w /2},
Z
Z
=
−
=
U
1
0
:
w
r
r
w
r – reszta z dzielenia (residue) liczby całkowitej (naturalnej) przez moduł w
Zauwa my, e
w
r
w
r
w
r
w
r
w
w
−
⊂
∨
⊂
∈
∀
:
:
:
:
:
Z
N
Z
N
N
•
N
7:5
=
{5, 12, 19, 26, …}
⊂
Z
7:–2
=
{…, –9, –2, 5, 12, 19, 26, …}
•
N
7:1
=
{1, 8, 15, 22, …}
⊂
Z
7:1
=
{…, –13, –6, 1, 8, 15, 22, …}
Systemy resztowe
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004
RNS–3
Podzielniki i liczby pierwsze
Podzielnik liczby w | N
⇔
N mod w
=
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 – k Y) wi c w | (X mod Y).
St d wynika, e w | (Y mod ( X mod Y)) itd., dopóki reszta nie jest równa 0.
Wtedy ostatni podzielnik jest NWD (X,Y).
X div w – iloraz całkowity X/w
X mod w – reszta z dzielenia całkowitego X/w
X = w
⋅
X div w + X mod w
( X
≡
X mod w) mod w
Systemy resztowe
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004
RNS–4
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 <N
2. Znajd w ci gu pierwsz liczb A ró n od 1 (jest na pozycji A
0
=(A+1)/2)
3. W miejsce ka dej liczby ci gu umieszczonej na pozycji A
0
+kA wpisz 0
4. Je eli A
2
< N, powró do 2, w przeciwnym razie zako cz
Najmniejsza wspólna wielokrotno
ś
ć
NWW (least common multiply, LCM)
[X
1
, X
2
,…, X
m
]
=
W
∈
N
⇔
∀
i: X
i
|W
∧
¬∃
Z
∈
N: (Z < W)
∧
∀
i: X
i
|Z
Systemy resztowe
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004
RNS–5
Funkcja Eulera (
ϕϕϕϕ
(N))
liczba liczb naturalnych <N wzgl
ę
dnie pierwszych z liczb
ą
N
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.,
T
WIERDZENIE
Je li podzielnikami N s liczby p
1
, p
2
, …, p
m
, czyli
∈
=
i
e
m
e
e
p
p
p
p
N
m
,
...
2
1
2
1
,
to
∈
−
−
−
=
i
m
m
p
p
p
p
p
p
p
N
N
,
1
...
1
1
)
(
2
2
1
1
ϕ
D
OWÓD
:
(przez indukcj
ę
lub wyprowadzenie na podstawie wy
Ŝ
ej podanego wnioskowania intuicyjnego)
Systemy resztowe
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004
RNS–6
Małe twierdzenie Fermata
Niech p b
ę
dzie liczb
ą
pierwsz
ą
za
ś
a nie jest podzielna przez p ((p, a) = 1).
Wówczas a
p–1
≡
1 mod p oraz a
p
≡
a mod p.
D
OWÓ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 Z
p:r
(
∀
1
≤
i
≠
j
≤
p – 1: i
⋅
a
≠
j
⋅
a mod p). A zatem
(1
⋅
a)(2
⋅
a)(3
⋅
a)…((p–1)
⋅
a) = a
p–1
(p–1)!
≡
(p–1)! mod p
Poniewa ((p–1)!, p) = 1 oraz (p, a) = 1, wi c ((a
p–1
– 1 )
⋅
(p–1)!, p) = p, a zatem
a
p–1
≡
1 mod p oraz a
⋅
a
p–1
≡
a mod p.
Wniosek: a
p–2
≡
a
–1
mod p
Twierdzenie Eulera
Je
ś
li
ϕ
(N) jest liczb liczb mniejszych od N i wzgl dnie pierwszych z N, to
1
mod
)
(
=
N
a
N
ϕ
oraz
N
a
a
N
mod
1
1
)
(
−
−
≡
ϕ
Systemy resztowe
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004
RNS–7
Chi skie twierdzenie o resztach
Niech W
=
{w
1
,w
2
,...,w
m
:
∀
i
≠
j: (w
i
,w
j
) = 1}oraz
∏
=
=
m
i
i
w
W
1
. Dla
0
≤
| X | < W
reprezentacja
X
=
〈
x
1
, x
2
, … , x
m
: x
i
=|
X | mod w
i
, w
i
∈
W
〉〉〉〉
jest unikatowa.
D
OWÓD
. Załó my, e
∃
0
≤
Y
< W, 0
≤
Z
< W, Y
≠
Z
:
∀
1
≤
i
≤
m
: Y
≡
Z
mod w
i
.
Zatem
∀
1
≤
i
≤
m
: w
i
| (Y
−
Z
), a poniewa W = [[w
1
,w
2
,…,w
m
]] , to W | (Y
−
Z
).
Skoro jednak Y
≠
Z
, to Y – Z
≥
W
, co przeczy zało eniu, wi c Y = Z
System RNS
(w
1
,w
2
,…,w
m
)
Reprezentacja X
=
〈
x
1
mod w
1
, x
2
mod w
2
, … , x
m
mod w
m
: w
i
∈
W
〉
w bazie W
•
x
i
∈
{0,1,...,w
i
−
1} dla kongruencji w zbiorze N,
•
x
i
∈
{–
w
i
/2
,…,
−
1,0,1,...,
w
i
/2
−
1
} dla kongruencji w zbiorze Z
W
NIOSEK
: W systemie RNS (w
1
,w
2
,…,w
m
),
∀
k
i
∈
N, 1
≤
i
≤
m
: |
〈
x
1
, x
2
, …,x
m
〉
|
≡
|
〈
x
1
±
k
1
w
1
, x
2
±
k
2
w
2
, … , x
m
±
k
m
w
m
〉
|mod w
i
Systemy resztowe
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004
RNS–
8
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
q
w
w
X
q
w
X
w
X
w
w
=
⇒
=
=
=
)
mod(
mod
mod
&
1
)
,
(
2
1
2
1
2
1
.
D
OWÓD
(pro ciej)
Je li X mod w
1
= q oraz X mod w
2
= q, to (X – q ) mod w
1
= 0 oraz (X – q ) mod w
2
= 0
zatem X – q = k
1
w
1
X – q = k
2
w
2
sk d wynika, e X – q = k w
1
w
2
, zatem
(X – q ) mod ( w
1
w
2
) = 0 , wi c X mod ( w
1
w
2
) = q.
W
ŁASNO
Ś
Ć
:
Je li a | X oraz a | w, to ( a X ) mod ( a w )
=
a
( X mod w )
( a X ) mod ( a w )
=
a X
−
a w a X / a w
=
a
( X
−
w X / w
)
=
a
( X mod w )
Odwrotno
ś
ć
multyplikatywna
(multiplicative inverse) w systemie RNS
1
mod
mod
1
=
⇔
=
−
w
zx
w
x
z
.
Systemy resztowe
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004
RNS–
9
Podzielno liczb (1)
w
w
w
x
w
x
k
i
i
i
k
i
i
i
mod
)
mod
)(
mod
(
mod
1
0
1
0
=
∑
∑
−
=
−
=
β
β
,
ale
i
i
)
1
(
)
1
mod(
1
)
1
mod(
m
m
=
±
⇒
=
±
β
β
β
β
,
wi c, poniewa 0
≤
x
i
≤
β
–1, mamy
)
1
(
mod
)
1
(
mod
1
0
1
0
−
=
−
∑
∑
−
=
−
=
β
β
β
k
i
i
k
i
i
i
x
x
)
1
(
mod
)
1
(
)
1
(
mod
1
0
1
0
+
−
=
+
∑
∑
−
=
−
=
β
β
β
k
i
i
i
k
i
i
i
x
x
⇒ 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
Je li
β
= a
k
±
1, to
1
mod
±
=
a
β
oraz
k
k
a
)
1
(
mod
±
=
β
⇒ reguły podzielno ci przez a w systemie o bazie
β
= a
k
±
1
785 mod 3 = (7+8+5) mod 3 = 20 mod 3 = 2
Systemy resztowe
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004
RNS–10
Podzielno liczb (2)
β
β
β
β
i
k
k
n
i
i
k
n
i
k
s
i
k
s
s
ik
i
n
i
i
X
x
x
∑
∑ ∑
∑
−
=
−
=
−
=
+
−
=
=
=
1
/
0
1
/
0
1
0
1
0
)
(
)
(
,
gdzie
β
s
k
s
l
ik
i
x
X
∑
−
=
+
=
1
0
s warto ciami cyfr po konwersji (
β
→
β
k
). Ale jest
j
k
kj
k
k
)
1
(
)
1
mod(
1
)
1
mod(
m
m
=
±
⇒
=
±
β
β
β
β
, zatem:
)
1
(
mod
)
1
(
mod
1
/
0
1
0
−
=
−
∑
∑
−
=
−
=
k
k
n
i
i
k
n
i
i
i
X
x
β
β
β
)
1
(
mod
)
1
(
)
1
(
mod
1
/
0
1
0
+
−
=
+
∑
∑
−
=
−
=
k
k
n
i
i
i
k
n
i
i
i
X
x
β
β
β
•
4533
10
mod 101
10
=
4533
10
mod (10
2
+
1)
10
=
(33
−45)
mod (10
2
+
1)
10
=
−
12
10
•
533
16
mod 0FF
16
=
533
16
mod (10
2
−
1)
16
=
(33
+5)
16
mod (10
2
−
1)
16
=
38
16
•
11011101110
2
mod 77
8
=
2356
8
mod (10
2
−
1)
8
=
(23
+
56)
8
mod (10
2
−
1)
8
=
2
8
Systemy resztowe
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004
RNS–11
Okresowo reszt
i
i
w
a
w
a
)
1
(
mod
1
mod
±
=
⇒
±
=
okres kongruencji k —
1
mod
:
&
mod
1
≠
<
∀
≡
w
k
s
w
s
k
β
β
półokres kongruencji k —
1
mod
:
&
mod
1
−
≠
<
∀
−
≡
w
k
s
w
s
k
β
β
reszty pot g baz
i
β
wzgl dem modułów
1
±
k
β
powtarzaj si okresowo
j
k
kj
k
k
)
1
(
)
1
mod(
1
)
1
mod(
m
m
=
±
⇒
=
±
β
β
β
β
⇒
)
1
mod(
)
1
(
)
1
mod(
±
=
±
+
k
s
j
k
s
kj
β
β
β
β
m
reszty pot g baz
i
β
wzgl dem modułów (
1
2
+
±
β
β
) powtarzaj si okresowo:
β
β
β
β
=
+
±
)
1
mod(
2
1
)
1
mod(
2
2
−
=
+
±
β
β
β
β
m
1
)
1
mod(
)]
1
(
[
)
1
mod(
2
2
3
±
=
+
±
−
=
+
±
β
β
β
β
β
β
β
m
Systemy resztowe
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004
RNS–12
Chi skie twierdzenie o resztach – konwersja odwrotna
Niech
W
=
{w
1
,w
2
,...,w
n
:
∀
i
≠
j: (w
i
,w
j
) = 1},
n
w
w
w
W
...
2
1
=
oraz
1
ˆ
−
=
s
s
Ww
w
.
Je
ś
li 0
≤
|
X | < W, to reprezentacja X
=
〈x
1
, x
2
, … , x
n
: x
i
=|
X | mod w
i
,w
i
∈
W〉 jest
unikatowa, przy tym
W
x
w
w
w
X
s
s
s
n
s
s
mod
)
mod
ˆ
(
ˆ
|
|
1
1
=
=
−
=
∑
X
gdzie
s
s
w
w
mod
ˆ
1
−
– odwrotno
ś
ć
multyplikatywna
s
w
ˆ wzgl
ę
dem modułu
s
w .
D
OWÓD
(nieformalny).
Je li
s
s
w
w
mod
ˆ
1
−
jest odwrotno ci multyplikatywn
s
w
ˆ , to 〈0, … , 0,1
s
, 0, … , 0〉
jest reprezentacj resztow
)
mod
ˆ
(
ˆ
1
s
s
s
w
w
w
−
w systemie RNS (w
1
,w
2
,…,w
m
), bo
liczba ta jest podzielna przez wszystkie w
i
z wyj tkiem w
s
.
Poniewa reszta z sumy jest równa sumie reszt, wi c
X
=
〈x
1
, x
2
, … , x
n
〉
=
x
1
⋅
〈1,0,…,0,0〉
+
x
2
⋅
〈0,1,…,0,0〉
+
…
+
x
n
⋅
〈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.
Systemy resztowe
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004
RNS–13
Chi skie twierdzenie o resztach – konwersja odwrotna
Niech
W
=
{w
1
,w
2
,...,w
n
:
∀
i
≠
j: (w
i
,w
j
) = 1},
n
w
w
w
W
...
2
1
=
oraz
1
ˆ
−
=
s
s
Ww
w
.
Je
ś
li 0
≤
|
X | < W, to reprezentacja X
=
〈x
1
, x
2
, … , x
n
: x
i
=|
X | mod w
i
,w
i
∈
W〉 jest
unikatowa, przy tym
W
x
w
w
w
X
s
s
s
n
s
s
mod
)
mod
ˆ
(
ˆ
|
|
1
1
=
=
−
=
∑
X
gdzie
s
s
w
w
mod
ˆ
1
−
– odwrotno
ś
ć
multyplikatywna
s
w
ˆ wzgl
ę
dem modułu
s
w .
D
O W Ó D
.
Niech
s
s
s
w
w
p
mod
ˆ
1
−
=
. Poniewa
s
s
w
X
x
mod
=
oraz
s
s
w
w
W
ˆ
=
, zatem
(
)
(
)
=
=
−
W
w
X
p
w
W
x
w
w
w
s
s
s
s
s
s
s
mod
)
mod
(
ˆ
mod
)
mod
ˆ
(
ˆ
1
(
)
(
)
W
p
w
X
W
w
X
w
X
p
w
s
s
s
s
s
s
mod
)
ˆ
(
mod
/
ˆ
=
−
=
,
i na podstawie zachowawczo ci kongruencji
(i)
W
p
w
X
W
p
w
W
X
W
p
w
X
s
n
s
s
s
n
s
s
s
n
s
s
mod
ˆ
mod
ˆ
)
mod
(
mod
ˆ
1
1
1
=
=
∑
∑
∑
=
=
=
.
Systemy resztowe
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004
RNS–14
Aby dowie prawdziwo ci tezy wystarczy wi c wykaza , e
1
mod
)
ˆ
(
1
=
∑
=
W
p
w
s
n
s
s
.
Poniewa z udowodnionego wcze niej lematu (2.49) wynika, e
(x,y) = 1
∧
a mod y
=
d
∧
a mod x
=
d
⇒ a mod xy
=
d
,
za
n
n
w
w
w
w
W
1
2
1
...
−
=
jest iloczynem liczb wzgl dnie pierwszych, wi c
wystarczy wykaza prawdziwo poprzednika implikacji
(ii)
1
mod
)
ˆ
(
1
mod
)
ˆ
(
:
1
1
=
⇒
=
∀
∑
∑
=
=
W
p
w
w
p
w
w
s
n
s
s
i
s
n
s
s
i
.
Ale
s
i
n
i
i
s
s
w
w
s
i
w
w
w
ˆ
/
:
1
ˆ
1
≠
∀
⇒
=
∏
=
, zatem
(iii)
1
mod
))
mod
ˆ
(
ˆ
(
mod
)
ˆ
(
mod
)
ˆ
(
1
1
=
=
=
−
=
∑
i
i
i
i
i
i
i
i
s
n
s
s
w
w
w
w
w
p
w
w
p
w
.
St d wynika prawdziwo nast pnika implikacji (ii), co dowodzi tezy.
Systemy resztowe
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004
RNS–
15
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 (2
k
–1,2
m
–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 = {2
k
+
1, 2
k
,
2
k
−
1}
W = {2
k
+
1, 2
k
,
2
k
−
1, 2
k
−
3}
W = {2
k
,
2
k
−
1, 2
i
−
1, …, 2
s
−
1, s < . . . < i < k, (s, …, i, k) = 1}
Systemy resztowe
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004
RNS–
16
Konwersja z systemu stałobazowego na system RNS(
ββββ
k
++++
1,
β
β
β
β
k
,
β
β
β
β
k
−−−−
1)
i
i
j
i
n
j
j
i
RNS
w
w
w
a
x
mod
)}
mod
)(
mod
(
{
:
1
0
β
β
∑
−
=
=
→
X
A
reguły podzielno ci ⇒ reguły konwersji z systemu naturalnego na RNS,
dla modułów o postaci
β
k
,
β
k
−
1 i
β
k
+
1.
β
β
β
β
i
k
s
i
i
i
k
l
k
l
l
ik
s
i
i
n
i
i
A
a
a
∑
∑
∑
∑
−
=
−
=
+
−
=
−
=
=
=
=
1
0
1
0
1
0
1
0
)
(
|
|
A
,
gdzie
β
l
k
l
l
ik
i
a
A
∑
−
=
+
=
1
0
s warto ciami cyfr liczby
A w systemie o bazie
β
k
.
Poniewa
1
0
−
≤
≤
k
i
A
β
, zatem
k
k
A
A
β
β
mod
mod
0
=
oraz
)
1
mod(
}
{
)
1
mod(
}
{
)
1
mod(
1
0
1
0
−
=
−
=
−
∑
∑
−
=
−
=
k
s
i
i
k
s
i
i
k
i
k
A
A
A
β
β
β
β
)
1
mod(
}
)
1
(
{
)
1
mod(
}
{
)
1
mod(
1
0
1
0
+
−
=
+
=
+
∑
∑
−
=
−
=
k
s
i
i
i
k
s
i
i
k
i
k
A
A
A
β
β
β
β
Systemy resztowe
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004
RNS–
17
Konwersja z systemu resztowego na system stałobazowy (CRT)
z
i
= 〈0,…,1
i
,…,0〉 – jedynki resztowe (wagi),
1
mod
=
i
i
w
z
i
0
mod
=
≠
i
j
i
w
z
Warto ci liczby X<W=
Π
w
i
o reprezentacji
〉
〈
0
1
,
,...,
x
x
x
n
jest zatem (CRT)
W
z
x
X
i
n
i
i
mod
)
(
1
∑
=
=
,
W celu wyznaczenia i-tej jedynki z
i
wystarczy wykona w
i
–1 oblicze . Mamy
1
mod
ˆ
1
,
ˆ
|
0
,...,
1
,...,
0
|
1
1
−
≤
=
≤
=
=
=
〉
〈
−
−
≠
∏
i
i
i
i
s
i
s
i
i
w
w
w
k
W
w
k
w
k
w
k
,
Obliczanie jedynek resztowych
)
mod
ˆ
(
ˆ
1
i
i
i
i
w
w
w
z
−
=
:
•
rozwi zanie równania
1
mod
))
mod
ˆ
(
ˆ
(
1
=
−
i
i
i
i
w
w
w
w
i
i
i
i
i
i
i
i
i
w
w
w
w
w
w
w
w
w
mod
)]
mod
ˆ
)(
mod
ˆ
[(
mod
))
mod
ˆ
(
ˆ
(
1
1
−
−
=
•
odwrócony algorytm Euklidesa – zapisujemy 1 jako sum wielokrotno ci
...
]
mod
div
[
)
mod
(
)
mod
(
1
1
1
=
+
⋅
⋅
−
⋅
=
⋅
−
⋅
=
−
−
x
n
x
n
x
k
n
x
x
n
k
n
x
x
•
małe twierdzenie Fermata ((p, a) = 1
→
a
p–1
≡
1 mod p
Systemy resztowe
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004
RNS–
18
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
j
w
ˆ
a
a
w
w
w
)
1
(
ˆ
2
1
3
+
=
=
,
2
1
2
mod
ˆ
3
3
=
⋅
=
w
w
)
1
)(
1
(
ˆ
3
1
2
−
+
=
=
a
a
w
w
w
,
1
)
1
(
1
mod
ˆ
2
2
−
=
−
⋅
=
w
w
)
1
(
ˆ
3
2
1
−
=
=
a
a
w
w
w
,
2
)
2
(
)
1
(
mod
ˆ
1
1
=
−
⋅
−
=
w
w
oraz ich odwrotno ci multyplikatywne (
i
i
i
w
w
w
mod
ˆ
ˆ
1
1
−
−
=
)
2
/
)
1
mod(
ˆ
1
)
1
mod(
ˆ
2
mod
ˆ
ˆ
1
3
1
3
3
3
1
3
a
a
w
a
w
w
w
w
=
−
⇒
=
−
⋅
=
−
−
−
,
1
mod
ˆ
1
mod
ˆ
1
mod
ˆ
ˆ
1
2
1
2
2
2
1
2
−
=
⇒
=
⋅
−
=
−
−
−
a
w
a
w
w
w
w
1
2
/
)
1
mod(
ˆ
1
)
1
mod(
ˆ
2
mod
ˆ
ˆ
1
1
1
1
1
1
1
1
+
=
+
⇒
=
+
⋅
=
−
−
−
a
a
w
a
w
w
w
w
St d
)
2
/
(
)
1
(
3
a
a
a
z
⋅
⋅
+
=
,
)
1
(
)
1
(
2
−
⋅
+
−
=
a
a
z
,
)
1
2
/
(
)
1
(
1
+
⋅
−
⋅
=
a
a
a
z
,
zatem warto ci liczby X o reprezentacji 〈r
3
, r
2
, r
1
〉 jest
X
=
(r
3
z
3
+ r
2
z
2
+ r
1
z
1
) mod (a + 1)
⋅
a
⋅
( a – 1).
Systemy resztowe
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004
RNS–
19
Konwersja z systemu resztowego na system stałobazowy – przykłady (1)
a
= 2
k
System resztowy (2
k
+1, 2
k
, 2
k
–1).
Mamy W = (2
k
+ 1)
⋅
2
k
⋅
( 2
k
– 1). Obliczymy liczby
j
w
ˆ
k
k
w
w
w
2
)
1
2
(
ˆ
2
1
3
+
=
=
,
2
1
2
mod
ˆ
3
3
=
⋅
=
w
w
)
1
2
)(
1
2
(
ˆ
3
1
2
−
+
=
=
k
k
w
w
w
,
1
)
1
(
1
mod
ˆ
2
2
−
=
−
⋅
=
w
w
)
1
2
(
2
ˆ
3
2
1
−
=
=
k
k
w
w
w
,
2
)
2
(
)
1
(
mod
ˆ
1
1
=
−
⋅
−
=
w
w
oraz ich odwrotno ci multyplikatywne
1
1
3
1
3
3
3
1
3
2
)
1
2
mod(
ˆ
1
)
1
2
mod(
ˆ
2
mod
ˆ
ˆ
−
−
−
−
=
−
⇒
=
−
⋅
=
k
k
k
w
w
w
w
w
,
1
2
mod
ˆ
1
2
mod
ˆ
1
mod
ˆ
ˆ
1
2
1
2
2
2
1
2
−
=
⇒
=
⋅
−
=
−
−
−
k
k
w
w
w
w
w
1
2
)
1
2
mod(
ˆ
1
)
1
2
mod(
ˆ
2
mod
ˆ
ˆ
1
1
1
1
1
1
1
1
1
+
=
+
⇒
=
+
⋅
=
−
−
−
−
k
k
k
w
w
w
w
w
St d
a
z
k
k
k
=
⋅
⋅
+
=
−
1
3
2
2
)
1
2
(
,
)
1
2
(
)
1
2
(
2
−
⋅
+
−
=
k
k
z
,
)
1
2
(
)
1
2
(
2
1
1
+
⋅
−
⋅
=
−
k
k
k
z
,
zatem warto ci liczby X o reprezentacji 〈r
3
, r
2
, r
1
〉
jest X
=
(r
3
z
3
+ r
2
z
2
+ r
1
z
1
) mod (2
2k
–1)
⋅
2
k
.
Systemy resztowe
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004
RNS–
20
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
X
10
.
Mamy W = 2
⋅3⋅7=42.
Obliczymy liczby
j
w
ˆ
6
/
ˆ
3
3
=
=
w
W
w
,
7
mod
6
1
mod
ˆ
3
3
≡
−
=
w
w
14
/
ˆ
2
2
=
=
w
W
w
,
3
mod
2
1
mod
ˆ
2
2
≡
−
=
w
w
21
/
ˆ
1
1
=
=
w
W
w
,
1
mod
ˆ
1
1
=
w
w
oraz ich odwrotno ci multyplikatywne
1
mod
ˆ
1
mod
ˆ
1
mod
ˆ
ˆ
3
1
3
3
1
3
3
3
1
3
−
=
⇒
=
⋅
−
=
−
−
−
w
w
w
w
w
w
w
,
1
mod
ˆ
1
mod
ˆ
1
mod
ˆ
ˆ
2
1
2
2
1
2
2
2
1
2
−
=
⇒
=
⋅
−
=
−
−
−
w
w
w
w
w
w
w
1
mod
ˆ
1
mod
ˆ
1
mod
ˆ
ˆ
1
1
1
1
1
1
1
1
1
1
±
=
⇒
=
⋅
±
=
−
−
−
w
w
w
w
w
w
w
St d z
3
= – 6
≡
36 mod 42, z
2
= – 14
≡
28 mod 42, z
3
= – 21
≡
21 mod 42,
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〉.
Systemy resztowe
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004
RNS–
21
Obliczanie odwrotno ci multyplikatywnych – (1)
Odwrócony algorytm Euklidesa
1
0
)
mod
(
)
mod
(
...
...
]
mod
div
[
)
mod
(
)
mod
(
1
1
1
1
1
+
⋅
=
⋅
−
⋅
+
⋅
−
⋅
⋅
=
=
=
+
⋅
⋅
−
⋅
=
⋅
−
⋅
=
−
−
−
−
p
n
D
n
x
C
n
B
n
x
A
p
x
n
x
n
x
k
n
x
x
n
k
n
x
x
Jedynki w systemie RNS (7,3,2) – mamy W = 2
⋅3⋅7=42.
Obliczymy liczby
j
w
ˆ
6
/
ˆ
3
3
=
=
w
W
w
,
7
mod
6
1
mod
ˆ
3
3
≡
−
=
w
w
14
/
ˆ
2
2
=
=
w
W
w
,
3
mod
2
1
mod
ˆ
2
2
≡
−
=
w
w
21
/
ˆ
1
1
=
=
w
W
w
,
1
mod
ˆ
1
1
=
w
w
oraz ich odwrotno ci multyplikatywne (
i
i
i
w
w
w
mod
ˆ
ˆ
1
1
−
=
−
)
t
t
w
t
w
t
w
w
t
w
w
−
−
⋅
=
⋅
+
⋅
−
=
−
=
⋅
−
⋅
=
−
−
−
−
)
ˆ
(
6
)
1
6
1
(
ˆ
6
7
ˆ
6
ˆ
ˆ
1
1
3
1
3
1
3
3
1
3
3
,
zatem
1
ˆ
czyli
,
1
oraz
0
ˆ
1
3
1
3
−
=
−
=
=
−
−
−
w
t
t
w
1
2
1
2
1
2
1
2
2
1
2
2
ˆ
)
ˆ
5
(
3
3
ˆ
)
1
5
3
(
3
ˆ
14
ˆ
ˆ
1
−
−
−
−
−
−
−
⋅
⋅
=
−
⋅
−
⋅
=
−
=
⋅
−
⋅
=
w
t
w
t
w
t
w
w
t
w
w
,
zatem
5
oraz
1
ˆ
1
2
−
=
−
=
−
t
w
1
1
1
1
1
1
1
1
1
1
1
1
ˆ
)
ˆ
10
(
2
2
ˆ
)
1
2
10
(
2
ˆ
21
ˆ
ˆ
1
−
−
−
−
−
+
−
⋅
⋅
=
−
⋅
+
⋅
=
−
=
⋅
−
⋅
=
w
t
w
t
w
t
w
w
t
w
w
,
zatem
10
oraz
1
ˆ
1
1
=
=
−
t
w
Systemy resztowe
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004
RNS–
22
Obliczanie odwrotno ci multyplikatywnych – (2)
Jedynki w systemie RNS (7,3,2) – małe twierdzenie Fermata
i
w
i
i
i
i
w
i
w
w
w
w
w
w
i
i
mod
)
ˆ
(
)
mod
ˆ
(
mod
)
ˆ
(
1
1
1
⋅
=
=
−
−
Mamy W = 2
⋅3⋅7=42.
Obliczymy liczby
j
w
ˆ
6
/
ˆ
3
3
=
=
w
W
w
,
7
mod
6
1
mod
ˆ
3
3
≡
−
=
w
w
14
/
ˆ
2
2
=
=
w
W
w
,
3
mod
2
1
mod
ˆ
2
2
≡
−
=
w
w
21
/
ˆ
1
1
=
=
w
W
w
,
1
mod
ˆ
1
1
=
w
w
oraz ich odwrotno ci multyplikatywne (
i
i
i
w
w
w
mod
ˆ
ˆ
1
1
−
=
−
)
7
mod
6
)
7
mod
6
)(
7
mod
6
(
7
mod
)
ˆ
(
1
1
7
1
1
7
3
−
−
−
−
=
≡
=
w
,
zatem
1
7
mod
6
ˆ
1
1
3
−
=
−
=
−
w
3
mod
14
)
3
mod
14
)(
3
mod
14
(
3
mod
)
ˆ
(
1
1
3
1
1
3
2
−
−
−
−
=
≡
=
w
,
zatem
1
3
mod
14
ˆ
1
1
2
−
=
=
−
−
w
2
mod
21
)
2
mod
21
)(
2
mod
21
(
2
mod
)
ˆ
(
1
1
2
1
1
2
1
−
−
−
=
≡
=
w
,
zatem
1
2
mod
21
ˆ
1
1
1
=
=
−
−
w
St d z
3
= – 6
≡
36 mod 42, z
2
= – 14
≡
28 mod 42, z
3
= – 21
≡
21 mod 42,
Systemy resztowe
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004
RNS–
23
System kwadratowo-resztowy QRNS
– arytmetyka liczb zespolonych (obliczanie transformaty Fouriera).
reprezentacja resztowa jednostki urojonej
1
i
−
=
.
1
mod
2
−
=
w
q
, ⇒
1
mod
−
=
w
q
.
problem: znalezienie zbioru modułów, dla których jest rozwi zanie równania
1
mod
2
−
=
w
q
.
D
EFINICJA
Liczb r, pierwsz wzgl dem
N
∈
w
i tak e równanie
r
w
x
=
mod
2
ma
rozwi zanie, nazywa si reszt
ą
kwadratow
ą
(quadratic residue) wzgl dem w.
Je eli natomiast równanie
r
w
x
=
mod
2
nie ma rozwi zania, to r nazywa si
nie-reszt
ą
kwadratow
ą
(quadratic nonresidue) wzgl dem w.
Systemy resztowe
© Janusz Biernat, Systemy resztowe'04, 26 grudnia 2004
RNS–
24
Reszty kwadratowe
Poniewa jest dokładnie (w
−
1) reszt niezerowych modulo w, a ka de równanie
r
w
x
=
mod
2
ma albo dwa rozwi zania nieprzystaj ce x oraz
−
x
(lub w
−
x
, bo
w
x
w
w
x
mod
)
(
mod
2
2
−
=
), 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
x
2
mod 13
=
r metod kolejnych prób dla x
=
1, 2,..., 6 (.x
2
≡
(w–x)
2
mod w)
Znajdujemy odpowiednio: 1
2
≡
1 mod 13, 2
2
≡
4 mod 13, 3
2
≡
−
4 mod 13,
4
2
≡
3 mod 13, 5
2
≡
−
1 mod 13, 6
2
≡
−
3 mod 13. Zatem resztami kwadratowymi
wzgl dem 13 s (w arytmetyce uzupełnieniowej):
−
4,
−
3,
−
1, 1, 3, 4.