Kryptografia-wyklad_08.pdf

Wykład 8

Potęgowanie

8.1 Funkcja Eulera

Deﬁnicja 8.1. Dla każdej liczby naturalnej m > 1 oznaczmy przez '(m) liczbę liczb

naturalnych mniejszych od m i względnie pierwszych z m, czyli

'(m) = rank Z m = |Z m |.

Poza tym przyjmijmy, że '(1) = 1. Tak określoną funkcję ' :

N ! N nazywamy funkcją

Eulera.

Przykład 8.1.

'(1) = 1,

'(2) = 2,

'(3) = 2,

'(4) = 2,

'(5) = 4,

'(6) = 2,

'(7) = 6,

'(8) = 4,

'(9) = 6,

'(10) = 4.

Twierdzenie 8.1. Niech p będzie liczbą pierwszą i k — liczbą naturalną. Wtedy

1 − 1

'(p k ) = p k

− p k−1 = p k

W szczególności, '(p) = p − 1.

Twierdzenie 8.2. Jeżeli m, n są względnie pierwszymi liczbami naturalnymi, to

'(mn) = '(m)'(n).

Uwaga 8.1. Własność funkcji ', o której mówi ostatnie twierdzenie, nazywamy mul

typlikatywnością. Ogólnie, funkcję f : N ! N nazywamy multyplikatywną, jeżeli dla

dowolnych liczb a?b zachodzi równość f (ab) = f (a)f (b).

Wniosek 8.1. Dla n 2 N oznaczmy D n = {p 2 P : p|n}. Wówczas

'(n) = n

1 − 1

p2D n

Przykład 8.2.

'(105) = '(3 · 5 · 7) = 105 ·

1 − 1

= 2 · 4 · 6 = 48.

8.2 Twierdzenia Eulera i Fermata

Twierdzenie 8.3 (Eulera). Jeżeli a, m są wzglednie pierwszymi liczbami naturalny

mi, to

a '(m)

1 (mod m).

Twierdzenie 8.4 (małe twierdzenie Fermata). Niech p 2 P i a 2 N. Wtedy

(a) spełniona jest kongruencja a p a (mod p),

(b) jeżeli liczba a nie jest podzielna przez p, to spełniona jest kongruencja

a p−1

1 (mod p).

Wniosek 8.2. Jeżeli a?m, to a −1 mod m = a '(m)−1 MOD m. W szczególności, jeżeli

p 2 P, to a −1 mod p = a p−2 MOD m.

Wniosek 8.3. Jeżeli a?m i r = n MOD '(m), to a n

a r

(mod m).

8.3 Szybkie potęgowanie modulo m

Algorytm potęgowania modulo m

Dane: Liczby naturalne b, m, n, gdzie b < m, oraz zapis binarny liczby n:

n = (n k−1 n k−2 . . . n 1 n 0 ) 2 =

n i 2 i , n i 2 {0, 1}.

i=0

Szukane: b n MOD m.

Zmienne pomocnicze: Liczba naturalna a.

Start

a := 1;

dla i = 0, 1, . . . , k − 1 wykonuj

jeżeli n i = 1, to a := a · b MOD m;

b := b 2 MOD m;

zwróć a

Stop

k−1

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: