Systemy resztowe'04, PWR, Semestr 3, Architektura komputerów, AK, biernat
[ Pobierz całość w formacie PDF ]
Systemy resztowe
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
Ŝ
ci
:
· zwrotna (
reflexive
):
N
º
N
mod
w
,
·
no
ś
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
.
© 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
8
N
w
:
r
=
{
N
Î
N
:
N
º
r
mod
w
; 0
£
r
<
w
},
N
=
N
w
:
r
r
=
0
· w zbiorze liczb całkowitych
Z
w
-
1
8
Z
w
:
r
= {
Z
Î
Z
:
Z
º
r
mod
w
;
-
w /
2
£
r
<
w /
2
},
Z
=
Z
w
:
r
r
=
0
r – reszta
z dzielenia (
residue
) liczby całkowitej (naturalnej) przez moduł
w
Zauwa my, e
"
w
Î
N
:
N
Ì
Z
Ú
N
Ì
Z
w
:
r
w
:
r
w
:
r
w
:
r
-
w
·
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, …}
© Janusz Biernat
,
Systemy resztowe'04, 26 grudnia 2004
RNS–
2
Systemy resztowe
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
© 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 <
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
© Janusz Biernat
,
Systemy resztowe'04, 26 grudnia 2004
RNS–
4
Systemy resztowe
Funkcja Eulera (
j
(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
e
m
Je li podzielnikami
N
s liczby
p
1
,
p
2
,
…
,
p
m
, czyli
N
=
p
e
p
e
...
p
,
p
Î
,
1
2
m
1
2
i
p
-
1
p
-
1
p
-
1
to
j
(
N
)
=
N
...
,
p
Î
1
2
m
i
p
p
p
1
2
m
D
OWÓ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 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
j (
N
) jest liczb liczb mniejszych od
N
i wzgl dnie pierwszych z
N
, to
j
(
N
)
a
mod
N
=
1
oraz
j
(
N
)
-
1
-
1
a
º
a
mod
N
© Janusz Biernat
,
Systemy resztowe'04, 26 grudnia 2004
RNS–
6
Systemy resztowe
Chi skie twierdzenie o resztach
m
Õ
=
Niech
W
= {
w
1
,
w
2
,...,
w
m
: "
i
¹
j
:
(
w
i
,
w
j
) = 1}
oraz
W
=
w
. Dla
0 £ |
X
|
< W
i
i
1
〈
x
1
,
x
2
, … ,
x
m
:
x
i
= |
X |
mod
w
i
, w
i
Î
W
〉
〉
jest unikatowa.
reprezentacja
X
=
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
© 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
(
w
,
w
)
=
1
&
X
mod
w
=
X
mod
w
=
q
⇒
X
mod(
w
w
)
=
q
.
1
2
1
2
1
2
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
.
:
Je li
a
|
X
oraz
a
|
w
, to (
a X
) mod (
a w
)
W
ŁASNO
Ś
=
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
z
=
x
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
b
mod
w
=
(
x
mod
w
)(
b
mod
w
)
mod
w
i
i
i
=
0
i
=
0
i
i
ale
b
mod(
b
±
1
=
@
1
⇒
b
mod(
b
±
1
=
(
@
1
,
wi c, poniewa 0 £
x
i
£ b –1, mamy
k
-
1
k
-
1
∑
i
∑
x
b
mod
(
b
-
1
=
x
mod
(
b
-
1
i
i
i
=
0
i
=
0
k
-
1
k
-
1
∑
i
∑
i
x
b
mod
(
b
+
1
=
(
-
1
x
mod
(
b
+
1
i
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
Je li b
= a
k
k
k
⇒
reguły podzielno ci przez
a
w systemie o bazie b
= a
k
±1, to
b
mod
a
=
±
1
oraz
b
mod
a
=
(
±
1
±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
n
/
k
-
1
k
-
1
∑
i
∑ ∑
s
k
i
∑
k
i
x
b
=
(
x
b
)
(
b
)
=
X
b
,
i
ik
+
s
i
i
=
0
i
=
0
s
=
0
i
=
0
X
∑
-
=
k
1
k
s
gdzie
=
x
s warto ciami cyfr po konwersji (b ®b
). Ale jest
b
i
ik
+
l
s
0
k
k
kj
k
j
b
mod(
b
±
1
=
@
1
⇒
b
mod(
b
±
1
=
(
@
1
, zatem:
n
/
k
-
1
n
-
1
∑
i
k
∑
k
x
b
mod
(
b
-
1
=
X
mod
(
b
-
1
i
i
i
=
0
i
=
0
n
/
k
-
1
n
-
1
∑
i
k
∑
i
k
x
b
mod
(
b
+
1
=
(
-
1
X
mod
(
b
+
1
i
i
i
=
0
i
=
0
4533
10
mod (10
2
mod (10
2
·
4533
10
mod 101
10
=
+
1)
10
=
(33
-45)
+
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
© Janusz Biernat
,
Systemy resztowe'04, 26 grudnia 2004
RNS–
10
[ Pobierz całość w formacie PDF ]