Systemy resztowe

© Janusz Biernat

, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009

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

+ Pa+abw) w

Iloraz całkowity X

div w (w ∈

∀X∈ : X − X mod w = w ⋅ X div w

Systemy resztowe

© Janusz Biernat

, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009

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

, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009

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

, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009

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

, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009

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)

NWW

(X

1

, X

2

,…, X

m

) =W∈ ⇔ ∀i: X

i

|W

∧ ¬∃Z∈ : (Z < W)∧ ∀i: X

i

|Z

Systemy resztowe

© Janusz Biernat

, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009

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

, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009

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

, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009

RNS–

8

Okresowo reszt

i

i

w

a

w

a

)

1

(

mod

1

mod

±

=

⇒

±

=

okres kongruencji

P(

β

,w)=k ⇔

1

mod

:

&

mod

1

≠

<

∀

≡

w

k

s

w

s

k

β

β

półokres kongruencji HP

(

β

,w)=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

, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009

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

, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009

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

, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009

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

, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009

RNS–

12

Chi skie twierdzenie o resztach – system RNS

Niech W

= {w

1

,w

2

,...,w

m

: ∀i ≠ j: NWD(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

, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009

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: NWD(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

, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009

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

, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009

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

, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009

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

, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009

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

, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009

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

, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009

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

, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009

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

, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009

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

, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009

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

β

β

β

β

β

β

β

Systemy resztowe*

© Janusz Biernat

, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009

RNS–

1*

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

, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009

RNS–

2*

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.

Systemy resztowe*

© Janusz Biernat

, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009

RNS–

3*

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

(formalny).

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

, AK1-5-09-Systemy resztowe.doc, 23 wrze nia 2009

RNS–

4*

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 wynika, e

NWD

(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.