ALGORYTMY ASYMETRYCZNE. PODSTAWY TEORETYCZNE.

1. Arytmetyka.

Niech n będzie dowolną liczbą naturalną, a x będzie liczbą całkowitą. Dla przez oznaczamy resztę z dzielenia x przez n. Np. , - 8mod10 = 2. Zbiór reszt modulo n, czyli oznaczamy przez . Mówimy, że x jest elementem odwrotnym do , jeśli . W tej sytuacji piszemy . Zbór elementów, dla których istnieją odwrotni w , oznaczamy przez . W zbiorze można wykonywać dwie operacje: x jest sumą y i z modulo n, jeśli ; x jest iloczynem y i z modulo n, jeśli . Jeśli n jest liczbą złożoną: n=pq, wtedy iloczyn pq jest równy zero w : n=pq=0 mod n. Piszemy , gdy i mówimy, że x i y są kongruentne modulo n.

Twierdzenie 1. Następujące warunki są ekwiwalentne

1.     ,

2.     , gdzie k jest liczbą całkowitą,

3.     , gdzie açb oznacza, że a dziele b.

Właściwości kongruencji

1.     if i then

2.     if i then

Przykład. Udowodnić że 73524 jest dzielone przez 11.

Oczywiście, że 10 º -1 (mod 11). Na mocy przedstawionej powyżej właściwości znajdujemy 100 º 1 (mod 11), 1000 º -1 (mod 11), 10000 º 1 (mod 11). Skąd 20 º -2 (mod 11), 500 º 5 (mod 11), 3000 º -3 (mod 11), 70000 º 7 (mod 11). Kolejne dodawanie daje 73520 º 7 (mod 11). Zatem 73520 +4 º 7+4 º 0 (mod 11).

Algorytm Euklidesa (3 wiek do n.e.) obliczania największego wspólnego dzielnika (NWD) liczb naturalnych a i b.

Oparty jest na wyrażeniach

NWD(a, b)=NWD(a, a mod b) dla a³b               (*)

NWD(a, 0)=a                                                                       (**)

Przykład. NWD (211, 79)? Kolejno wykorzystujemy wzór (*) póki nie otrzymamy (**)

211=79*2+53

79=53*1+26

53=26*2+1

26=1*26+0

Mamy NWD(211, 79) =NWD(79, 53) =NWD(53, 26) =NWD(26, 1)= =NWD(1,0)=1.

W ogólnym przypadku działania algorytmu Euklidesa można wyznaczyć następująco:

1.     Położyć

2.     Przy i-tej iteracji obliczyć

3.     if then i=i+1 goto 2

4.     if then NWD (a, b)=

5.     End

Ilość kroków m algorytmu Euklidesa definiowana jest nierównością .

W trakcie działania algorytmu Euklidesa można wyznaczyć liczby całkowite x, y, taki że   ,

gdzie a i b względnie pierwsze: NWD(a, b)=1, a>0, b>0.

Niech , gdzie

wtedy

; .

Te obliczenia zręcznie prowadzić za pomocą tabeli

Przykład. Wyznaczyć liczby całkowite x, y, taki że

17 x -  13 y = 1

Mamy

17 = 13*1 + 4                            =1

13 = 4*3 + 1                            =3

4 = 1*4 + 0                                          =4

Zatem