Systemy resztowe
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa
ź
dziernika 2006
RNS–1
Kongruencje
Liczby kongruentne (przystaj ce) modulo w
∈
(w – moduł przystawania)
∀
(N,M
∈
): N
≡
M (mod w)
⇔
∃
k
∈
: N
−
M
=
kw
∨
M
−
N
=
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).
L
EMAT
: Kongruencja jest zachowawcza (oboj tna, indifferent) wobec ka dego
z działa : dodawania, odejmowania, mno enia (
♦
)
N
≡
M (mod w)
∧
Q
≡
P (mod w) ⇒ N
♦
Q
≡
M
♦
P (mod w) .
D
OWÓ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 X div w (w
∈
∀
X
∈
: X
−
X mod w = w
⋅
X div w
Systemy resztowe
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa
ź
dziernika 2006
RNS–2
Klasy kongruencji
Klasy kongruencji (równowa no ci wzgl dem relacji przystawania)
w:r
=
{ Z
∈
: Z
≡
r (mod w) ;
−
w /2
≤
r < w /2},
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 r
≥
0 i mamy:
w:r
⊂
w:r
∨
w:r
⊂
w:r–w
•
7:5
=
{5, 12, 19, 26, …}
⊂
7:–2
=
{…, –9, –2, 5, 12, 19, 26, …}
•
7:1
=
{1, 8, 15, 22, …}
⊂
7:1
=
{…, –13, –6, 1, 8, 15, 22, …}
D
EFINICJE
Podzielnik p
∈
liczby Q
∈
p|Q
⇔
Q mod p
=
0, p
∈
Odwrotno (multyplikatywna) x
–1
mod w liczby x modulo w
a = x
–1
mod w
⇔
a x mod w= 1
! (je li x i w maj wspólny podzielnik p
≠
1, to z
⋅
x mod w =1 nie ma rozwi zania)
Systemy resztowe
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa
ź
dziernika 2006
RNS–3
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 )
T
WIERDZENIE
:
Dla dowolnych liczb naturalnych n i m, je li m < n oraz p = NWD (m, n), to:
1. liczba p jest te najwi kszym wspólnym dzielnikiem m oraz n mod m.
2. istniej takie liczby całkowite u oraz v, e p = u n + v m (najwi kszy wspólny
dzielnik mo na przedstawi jako kombinacj liniow liczb m oraz n).
D
OWÓD
:
1. Je li p = NWD (m, n), to m = k
m
p oraz n = k
n
p , to n
−
m = ( k
n
−
k
m
) p , wi c
m < n ⇒ p = NWD (m, n )= NWD (m, n mod m)
2. Je li p = NWD (n, m ), to m = k
m
p, n = k
n
p oraz NWD (k
n
, k
m
) = 1. Mamy zatem
v m = v k
m
p, u n = u k
n
p i v k
m
+u k
n
= 1. Poniewa NWD (k
n
, k
m
) = 1, wi c ka da
liczba u k
n
dla u = 1 , 2 , … , k
m
−
1 nale y do innej klasy kongruencji modulo k
m
.
Istnieje wi c takie u, e u k
n
= s k
m
+1. Równo jest spełniona gdy v =
−
s .
Systemy resztowe
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa
ź
dziernika 2006
RNS–4
Wła ciwo ci reszt
Liczby wzgl dnie pierwsze (relatively prime): NWD (X, Y )
=
1.
L
EMAT
:
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
:
Je li X mod w
1
= q i X mod w
2
= q, to (X – q ) mod w
1
= 0 i (X – q ) mod w
2
= 0 . Zatem
X – q = k
1
w
1
i X – q = k
2
w
2
, wi c X – q = k w
1
w
2
oraz X mod w
1
w
2
= q
L
EMAT
: Kongruencje mo na dzieli obustronnie przez wspólny czynnik:
(a X ) mod (aw)
=
a (X mod w)
D
OWÓD
:
( a X ) mod ( a w )
=
a X
−
a w a X / a w
=
a ( X
−
w X / w )
=
a ( X mod w )
Systemy resztowe
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa
ź
dziernika 2006
RNS–5
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
∈
⇔
∀
i: X
i
|W
∧
¬∃
Z
∈
: (Z < W)
∧
∀
i: X
i
|Z
Systemy resztowe
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa
ź
dziernika 2006
RNS–6
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, 05-06-Systemy resztowe.doc, 7 pa
ź
dziernika 2006
RNS–7
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, 05-06-Systemy resztowe.doc, 7 pa
ź
dziernika 2006
RNS–8
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, 05-06-Systemy resztowe.doc, 7 pa
ź
dziernika 2006
RNS–9
Małe twierdzenie Fermata
T
WIERDZENIE
Niech p b dzie liczb pierwsz . Je li p nie jest podzielnikiem liczby a, to
wtedy a
p–1
≡
1 (mod p) za dla dowolnego a zachodzi a
p
≡
a (mod p) .
D
OWÓD
.
Skoro p nie dzieli a, to
∀
1
≤
i
≠
j
≤
p – 1: i
⋅
a
≠
j
⋅
a mod p, wi c ka da liczba ci gu
1
⋅
a, 2
⋅
a, 3
⋅
a, …, (p – 1)
⋅
a nale y do innej klasy resztowej
p:r
, r = 1, 2, ..., p – 1.
A zatem [(1
⋅
a)(2
⋅
a)(3
⋅
a)…((p –1)
⋅
a)] mod p = (p –1)! mod p, czyli
a
p–1
(p–1)!
≡
(p –1)!(mod p)
Poniewa NWD(p, a) = 1, wi c NWD(p, (a
p–1
– 1 )
⋅
(p –1)!) = p, (bowiem (p –1)!
nie dzieli si przez p). St d wynika, e
a
p–1
≡
1 (mod p)
i poniewa p nie dzieli a, wi c a
⋅
a
p–1
≡
a (mod p) , a zatem
a
p
≡
a (mod p)
Je li NWD(p, a) = p, to ostatnia zale no jest trywialna (a mod p = 0)
Systemy resztowe
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa
ź
dziernika 2006
RNS–10
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.
T
WIERDZENIE
Je li podzielnikami liczby N s p
1
, p
2
, …, p
m
, czyli
m
e
m
e
e
p
p
p
N
...
2
1
2
1
=
, p
i
∈
, to
liczb naturalnych mniejszych od N i wzgl dnie pierwszych z liczb N jest
∏
=
=
−
−
=
m
i
i
e
i
i
i
p
p
N
1
1
)
1
(
)
(
ϕ
, p
i
∈
D
OWÓD
:
Je li p
i
jest podzielnikiem N, to w zbiorze {1, 2, …, N} jest N– N(p
i
)
–1
liczb
niepodzielnych przez p
i
. [N– N(p
i
)
–1
]– [N– N(p
i
)
–1
] (p
j
)
–1
= N (1– (p
i
)
–1
)(1– (p
j
)
–1
)
spo ród nich nie jest podzielnych przez p
j
. (co p
j
-ta spo ród N i spo ród |p
i
)
Je li wi c p
i
i=1, 2, ..., m s liczbami pierwszymi, to w zbiorze {1, 2 , … , N} jest
)
1
)...(
1
)(
1
(
...
)
1
)...(
1
)(
1
(
...
2
1
1
1
2
1
1
1
1
2
1
1
2
1
2
1
2
1
−
−
−
=
−
−
−
−
−
−
−
−
−
m
e
m
e
e
m
e
m
e
e
p
p
p
p
p
p
p
p
p
p
p
p
m
m
liczb niepodzielnych przez adn z nich.
W
NIOSEK
: Je li NWD(N,M)=1, to
ϕ
(MN) =
ϕ
(M)
ϕ
(N) .
Systemy resztowe
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa
ź
dziernika 2006
RNS–11
Twierdzenie Eulera
T
WIERDZENIE
Je li
ϕ
(N) jest liczb liczb mniejszych od N i wzgl dnie pierwszych z N, to
1
mod
)
(
=
N
a
N
ϕ
D
OWÓD
.
Je li N = p twierdzenie jest prawdziwe (
ϕ
(p) = p –1) (małe tw. Fermata).
Załó my, e twierdzenie jest prawdziwe dla N = p
m
, czyli
m
p
p
p
a
m
mod
1
)
1
(
1
≡
−
−
.
St d wynika, e
m
p
p
kp
a
m
+
=
−
−
1
)
1
(
1
oraz
m
p
m
p
p
Kpp
kp
a
m
+
=
+
=
−
1
)
1
(
)
1
(
, zatem
1
)
1
(
mod
1
+
−
≡
m
p
p
p
a
m
. Twierdzenie jest wi c prawdziwe dla N = p
α
, czyli
1
mod
)
(
=
m
p
p
a
m
ϕ
Je li wi c
h
b
a
t
q
p
N
...
=
, to
1
mod
)
(
mod
)
...
(
)
(
)
...
(
=
=
a
t
q
p
a
t
q
p
p
a
p
a
h
b
a
h
b
a
ϕ
ϕ
ϕ
oraz
1
mod
)
(
mod
)
...
(
)
(
)
...
(
=
=
b
t
p
q
b
t
q
p
q
a
q
a
h
a
b
h
b
a
ϕ
ϕ
ϕ
itd.. St d wynika teza twierdzenia:
1
)
...
(
mod
)
...
(
=
h
b
a
w
q
p
w
q
p
a
h
b
a
ϕ
, czyli
1
mod
)
(
=
N
a
N
ϕ
W
NIOSEK
:
)
(mod
1
1
)
(
N
a
a
N
−
−
≡
ϕ
Systemy resztowe
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa
ź
dziernika 2006
RNS–12
Chi skie twierdzenie o resztach – system RNS
Niech W
=
{w
1
,w
2
,...,w
m
:
∀
i
≠
j: NWP(w
i
,w
j
) = 1} za
∏
=
=
m
i
i
w
W
1
Reprezentacja
X
=
〈x
1
,
x
2
, … ,
x
m
:
x
i
=
X mod w
i
, w
i
∈
W〉〉〉〉
ka dej liczby 0
≤
X < W jest unikatowa.
D
OWÓD
. Załó my, e
∃
0
≤
X , Y < W, Y
≠
X:
∀
1
≤
i
≤
m : Y
≡
X mod w
i
. Zatem
∀
1
≤
i
≤
m : w
i
| (
Y
−
X), a poniewa W = NWW(w
1
,
w
2
,…,
w
m
), to
W | (Y
−
X).
Skoro jednak
Y
≠
X, to Y – X
≥
W, co przeczy zało eniu, wi c Y = X
System resztowy RNS (w
1
,
w
2
,…,
w
m
) (
Residue Number System)
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 ,
•
x
i
∈
{–
w
i
/2,…,
−
1,0,1,...,
w
i
/2
−
1} dla kongruencji w zbiorze
W
NIOSEK
: W systemie
RNS (w
1
,
w
2
,…,
w
m
),
∀
k
i
∈
,
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
〉|modw
i
Systemy resztowe
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa
ź
dziernika 2006
RNS–13
Chi skie twierdzenie o resztach – konwersja odwrotna
C
HI SKIE TWIERDZENIE O RESZTACH
(CRT)
(S
UN
-T
ZU
,
III W
., Q
IN
J
IUSHAO
, 1247)
Niech W
=
{
w
1
,
w
2
,...,
w
n
:
∀
i
≠
j: NWP(w
i
,
w
j
) = 1},
n
w
w
w
W
...
2
1
=
. Reprezentacja
〈x
1
, x
2
, … , x
n
: x
i
=
X mod w
i
, w
i
∈
W〉
ka dej liczby 0
≤
X < W jest unikatowa oraz
W
x
w
w
w
X
s
s
s
n
s
s
mod
)
mod
ˆ
(
ˆ
|
|
1
1
=
=
−
=
∑
X
gdzie
1
ˆ
−
=
s
s
Ww
w
, za
s
s
w
w
mod
ˆ
1
−
– odwrotno
s
w
ˆ wzgl dem modułu
s
w .
D
OWÓD
(nieformalny szkic dowodu konwersji odwrotnej).
Ze wzgl du na zachowawczo kongruencji wobec dodawania mamy
〈x
1
, x
2
, … , x
n
〉
=
x
1
⋅
〈1,0,…,0,0〉
+
x
2
⋅
〈0,1,…,0,0〉
+
…
+
x
n
⋅
〈0,0,…,0,1〉 .
W systemie RNS (w
1
,w
2
,…,w
m
) liczba p
s
o reprezentacji 〈0, … , 0,1
s
, 0, … , 0〉 jest
podzielna przez ka de w
i
oprócz w
s
, jest wi c
s
s
w
k
p
ˆ
⋅
=
(liczby p
s
istniej , bo
ró nych reprezentacji jest dokładnie W). Poniewa jej reszta wzgl dem w
s
jest
równa 1, wi c
s
s
w
w
k
mod
ˆ
1
−
=
jest odwrotno ci
s
w
ˆ oraz
)
mod
ˆ
(
ˆ
1
s
s
s
s
w
w
w
p
−
=
.
〈x
1
, x
2
, … , x
n
〉 jest wi c reprezentacj liczby (x
1
p
1
+ x
2
p
2
+ … + x
n
p
n
) mod W.
Systemy resztowe
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa
ź
dziernika 2006
RNS–14
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, 05-06-Systemy resztowe.doc, 7 pa
ź
dziernika 2006
RNS–15
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, 05-06-Systemy resztowe.doc, 7 pa
ź
dziernika 2006
RNS–16
Konwersja z systemu resztowego na system stałobazowy (CRT)
p
i
= 〈0,…,1
i
,…,0〉 – jedynki resztowe (wagi),
1
mod
=
i
i
w
p
i
0
mod
=
≠
i
j
i
w
p
Warto ci liczby
X<W=
Π
w
i
o reprezentacji
〉
〈
n
x
x
x
,...,
,
2
1
jest zatem (CRT)
W
p
x
p
x
p
x
X
n
n
mod
)
...
(
2
2
1
1
+
+
+
=
,
W celu wyznaczenia
i-tej jedynki p
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
p
−
=
:
•
rozwi zanie równania
1
mod
))
mod
ˆ
(
ˆ
(
1
=
−
i
i
i
i
w
w
w
w
, czyli
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
−
−
=
(... je li
a x mod w =
−1
, to
a
2
x mod w = x
– 1
mod
w )
•
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
•
twierdzenie Eulera:
)
(mod
1
1
)
(
N
a
a
N
−
−
≡
ϕ
Systemy resztowe
© Janusz Biernat, 05-06-Systemy resztowe.doc, 7 pa
ź
dziernika 2006
RNS–17
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, 05-06-Systemy resztowe.doc, 7 pa
ź
dziernika 2006
RNS–18
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, 05-06-Systemy resztowe.doc, 7 pa
ź
dziernika 2006
RNS–19
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, 05-06-Systemy resztowe.doc, 7 pa
ź
dziernika 2006
RNS–20
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, 05-06-Systemy resztowe.doc, 7 pa
ź
dziernika 2006
RNS–21
Obliczanie odwrotno ci multyplikatywnych – (2)
Jedynki w systemie RNS (7,3,2) – twierdzenie Eulera
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, 05-06-Systemy resztowe.doc, 7 pa
ź
dziernika 2006
RNS–22
Wyznaczanie reprezentacji resztowych
1. Z twierdzenia Fermata lub Eulera – reszty pot g – redukcja pot gi mod
ϕ
(
p)
a
x
mod
N = ( a
ϕ
(p)
)
[ x div
ϕ
(p) ]
a
x mod
ϕ
(p)
mod
N = a
x mod
ϕ
(p)
mod
N
Ponadto
p
p
a
p
a
p
a
p
a
p
a
x
x
x
x
X
i
i
mod
...]
)
mod
(
)
mod
(
)
mod
[(
mod
mod
2
2
1
0
2
2
2
=
∑
=
2. Poniewa dla liczby naturalnej
a>3
a mod a
±
1=
−
(
±
1) ⇒
a
k
mod
a
±
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,…)
)
1
mod(
)
1
(
)
(
)
1
mod(
)
(
)
1
mod(
/
0
1
0
/
0
1
0
1
0
±
±
=
=
±
=
±
∑ ∑
∑ ∑
∑
=
−
=
+
=
−
=
+
−
=
k
j
k
n
j
k
i
i
i
kj
k
k
n
j
kj
k
i
i
i
kj
k
n
i
i
i
x
x
x
β
β
β
β
β
β
β