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.