Str126

24H OdpowiniH do ćwlo/cń

S7iach, by znaleźć liczbę x taką, że _rv - 1 (mod p“) i x ~ -1 (mod m').

Pokaż, że ta liczba x jest kontr przykładem na (a).

8.    Połącz w pary liczby całkowite z przedziału od 1 do p — 1 z liczbami odwrotnymi do nich modulo p. Zgodnie z ćwiczeniem 7(a) tylko liczby li -1 są swoimi odwrolnościami. Zatem, jeśli pomnożymy przez siebie te p - 1 liczb, to każda para odwrotności skróci się i pozostaną tylko liczby li — 1.

9.    Oczywiście liczba 4 ma żądaną własność, ale nie jest trzycyfrowa. Z chińskiego twierdzenia o resztach wynika, że każda inna liczba dająca żądane reszty musi różnić się od 4 o wielokrotność liczby 7*9 11 = 693. Jedyną taką liczbą trzycyfrową jest 4 + 693 = 697.

10.    Można zastosować chińskie twierdzenie o resztach do kongruencji * s 1 (mod 11), x = 2 (mod 12), x = 3 (mod 13). Inaczej, można zaobserwować, że liczba —10 oczywiście daje właściwe reszty, a następnie postępować jak w ćwiczeniu 9, by otrzymać —10 + 11 • 12 • 13 = 1706.

11.    (a) 1973; (b) 63841; (c) 58837.

12.    Iloraz daje reszty 5, 1, 4 przy dzieleniu przez 9, 10 i 11, a więc jest postaci 851 + 990/zi (co wynika z chińskiego twierdzenia o resztach). Podobnie dzielnik ma postać 817 + 990/z. Ma on tylko trzy cyfry, więc n = 0. Ponieważ dzielna ma 6 cyfr, więc także m — 0. Zatem iloraz jest równy 851.

13.    Najwięcej czasu przy korzystaniu z chińskiego twierdzenia o resztach zużywa się na: (i) obliczenie M\ (ii) obliczenie M_{ — Mlm_t dla każdego spośród r różnych z; (iii) znalezienie liczb odwrotnych do M_{ modulo m_l dla wszystkich z; (iv) obliczenie iloczynów a_iM_lN_i dla wszystkich i we wzorze na x\ (v) podzielenie otrzymanego x przez M, by uzyskać najmniejsze nieujemne rozwiązanie układu kongruencji. Będziemy zakładać, że liczby m_t, a_{ oraz

mają po 0(logi?) bitów, natomiast M i mają po 0(rlog2?) bitów. To daje nam 0(r²Iog²i?) operacji na bitach w (i)-(ii) oraz (iv)-(v). W (iii) potrzebujemy 0(r²log²i?) operacji, by zredukować każdą liczbę M_{ modulo m_l przed obliczeniem odwrotności, a potem 0(rlog³£) operacji na bitach, by za pomocą algorytmu Euklidesa znaleźć wszystkie r odwrotności. To daje łącznie oszacowanie rzędu 0(r log² i?(r + logii)). To, który składnik, r²Iog²J? czy rlog³£, dominuje, zależy od względnej wielkości r i logi? (tzn. od liczby kongruencji i liczby cyfr w modułach).

14.    38^1+2+2S+2# s 38 • 2 • 16 • 63 = 79 (mod 103).

15.    Jeśli skorzystamy z oszacowania 0(k²) na liczbę operacji na bitach potrzebnych do pomnożenia przez siebie dwóch liczb ^-bitowych (jak dotychczas robiliśmy), to nie zyskujemy czasu. Faktycznie, ostatnie mnożenie wymaga czasu 0((nlog6)²) i takie samo oszacowanie otrzymamy dla mnożenia b przez siebie n razy. Trudność polega na tym, że w przeciwieństwie do mnożenia modulo m metoda iterowanego podnoszenia do kwadratu wymaga tu mnożenia przez siebie bardzo dużych liczb, co równoważy zysk pochodzący z tego, że mamy mniej mnożeń do wykonania. Jeśli natomiast skorzystamy z jakiejś sprytniejszej metody mnożenia liczb A:-bito-

Odpowiedzi do ćwiczeń 249

wych, na przykład użyjemy algorytmu wymagającego tylko 0(k!og&iog-logik) operacji na bitach, to zaoszczędzimy czas, stosując metodę i terowanego podnoszenia do kwadratu.

16.    (a) Obie metody wymagają 0(log³p) operacji na bitach.

(b) Metoda iterowanego podnoszenia do kwadratu nadal wymaga czasu rzędu 0(JogV), natomiast po wykonaniu pierwszego kroku algorytmu Euklidesa - podzieleniu p przez a (wymagającego 0(log/? log a) operacji na bitach) - dokończenie algorytmu Euklidesa będzie wymagało 0(log³fl) operacji na bitach. Zatem algorytm Euklidesa jest szybszy dla a znacznie mniejszych od p.

17.    n 90 91 92 93 94 95 96 97 98 99 100 tp(n) 24 72 44 60 46 72 32 96 42 60 40

18.    Nie istnieje liczba n, dla której g>(n) jest liczbą nieparzystą większą od 1; (p(n) = 1 dla fi — 1,2; ę(ń) = 2 dla n = 3,4,6; tp(ń) = 4 dla n = 5.8,10,12; (p{ń) = 6 dla n = 7,9,14,18; cp(n) = 8 dla n = 15,16,20,24, 30; cp(n) = 10 dla n = 11, 22; (p(ri) = 12 dla n = 13,21,26,28, 36,42. Aby na przykład dowieść, że to są wszystkie wartości n, dla których <?(n)= 12, porównaj możliwe rozkłady 12 na czynniki (dopuszczamy czynnik 1, ale nie dopuszczamy 3) ze wzorem (p(Hp*) = H(p* - p*^-1). Mamy rozkłady 1 ■ 2 • 6, 1 • 12,2 • 6 i 12. Pierwszy daje 2 • 3 • 7, drugi daje 2 • 13, trzeci daje (3 lub 4) * 7 oraz 4 ■ 9 i czwarty daje 13.

19.    Liczba n nie może być pierwsza, gdyż wtedy mielibyśmy ę(n) = n - 1. Z założenia n nie jest kwadratem liczby pierwszej. Gdyby nie była ona iloczynem dwóch różnych liczb pierwszych, to byłaby iloczynem trzech lub więcej liczb pierwszych (niekoniecznie różnych). Niech p będzie najmniej

szą z nich. Wtedy p<n^1/3, skąd otrzymujemy ę(ń) < n    ^

^n(l — n^-1/3) = n-n^2/3, sprzeczność.

20.    Pokaż, że kwadrat dowolnej liczby nieparzystej przystaje do 1 modulo 8, a następnie zastosuj indukcję tak samo jak w pierwszym akapicie dowodu twierdzenia 1.3.5.

21.    (a) Zauważmy, że 360 jest wielokrotnością liczby ę?(p*) dla wszystkich

p^a\\m. Z uwagi sformułowanej przed przykładem 3 w tekście książki wynika, że 6647³⁶² = 6647² = 44182609 (mod m) (korzystamy tu również z tego, że NWD(6(A7, m) = 1, co wynika z rozkładu 6647 = 17² • 23.)

(b) Podnieśmy a do potęgi 359 modulo m za pomocą metody iterowanego podnoszenia do kwadratu. Ponieważ m- (101100111),, więc będziemy 8 razy podnosić do kwadratu i 5 razy mnożyć przez siebie liczby co najwyżej 63-bitowe, za każdym razem wynik (co najwyżej 126-bitowy) będziemy dzielić przez liczbę 63-bitową. Tak więc łączna liczba operacji na bitach wynosi co najwyżej 13 • 63 • 63 + 13 • 64 • 63 = 104013.