Str131

?>56 Odpowiedź do MewA

|9. n » 3; p - I - 2⁵ • 65; r m a*^y •» 201 (mod p) (obliczamy 302^s* metodą i terowanego podnoszenia do kwadratu, podnosząc do kwad rat u kolejno 5 razy i mnożąc wynik prze* 102); także za pomocą metody iterowanego podnoszenia do kwadratu obliczamy b b «•* s 888 (mod p); bierzemy / *= 2^a, tz.n. >/302 mod p “ b^Ąr m 1292 (mod p).

20. (a) Zastosuj indukcję względem a. W kroku indukcyjnym, gdy przechodzimy od a - I do a, zakładamy, że x jest (a — l)-cyfrową liczbą w systemie o podstawie p taką. że v² = a (mod p^{B_ 1}). Aby znaleźć ostatnią cyfrę V, , e{0, I, .... p — 1} liczby .v = j? + x_a_,p“^_I, przyjmijmy j?^a - a + bp*~¹ dla pewnej liczby b i wykonajmy następujące obliczenia modulo p“:    x² - (X + x^_lp*~¹)² s Z¹ -|- 2x₀x_a„_lp*~^l =

= a + p*~^l(b -f 2.v₀a'_o„ ,). Wystarczy zatem, by x_a__i s —(2x₀)~^lb (mod p) (zauważ, że 2x₀ jest elementem odwracalnym, gdyż liczba p jest nieparzysta i liczba a jest względnie pierwsza z p, bo a = xj (mod p)).

(b) Skorzystaj z chińskiego twierdzenia o resztach, by znaleźć x przystający modulo p“ do pierwiastka kwadratowego znalezionego w (a).

21. (a) Gdyby relacja (*) była spełniona dla b₂ i b_lb₂, to po podzieleniu obu kóńgrucncji stronami otrzymalibyśmy relację (*) dla b₂ (gdyż obie strony są multyplikatywne). Następnie załóżmy, że relacja (*) nie jest spełniona dla pewnej liczby b. Wtedy zbiór tych b, które otrzymujemy przez pomnożenie b przez wszystkie elementy, dla których relacja (*) jest spełniona, składa się z tych liczb, dla których relacja (*) nie zachodzi.

(b) Na przykład weźmy 6= 1 + n/p, gdzie p²|». Wtedy (—)= 1, ale

b^J = 1 tylko dla p\j, co nie zachodzi dla j — (n — l)/2.

= — 1, ale ó⁽"~^1)/2 = 1 (mod n/p), skąd wynika,

(c) Pokaż, że

ze

£(*-i)/2 _nj_{e mo}ż_e przystawać do —1 modulo n/p, a więc tym bardziej modulo n. Następnie niech a₁ będzie dowolną nieresztą kwadratową modulo p i niech a₂ = 1. Skorzystaj z chińskiego twierdzenia o resztach, by znaleźć rozwiązanie b układu kongruencji x = a_l (mod p), x = a₂ (mod nip).

22. b¹ = (/ + oc)^p(ł + a) = (/ + a^p)(/ + a) = (t - a)(t -f a) = f² — a² = a, gdzie trzecia równość wynika z tego, że elementem sprzężonym

z a

a jest a*

zauważ, że b musi należeć do F.

gdyż a ma z założenia dwa pierwiastki kwadratowe w F_p, a więc pierwiastki kwadratowe z a w ciele Fj faktycznie należą do F_.

przez p; wtedy b jest pierwiast

23. Niech b będzie resztą z dzielenia n

kiem kwadratowym z — 1 modulo p, tzn. p|ó² + 1. Oblicz teraz c + di — — NWD(p, b + 0 (por. ćwiczenie 14 z podrozdziału 1.2).

3,1

1.    Wc scwetl a smilc on a hont'% as*, and a year later it was elected Presi-dent.” (Przyszyliśmy uśmiech do końskiego zadu i rok później został on wybrany na prezydenta.)

2.    Skorzystaj z tego, że „X" występuje najczęściej w kryptografie, by otrzymać b ~ 19. Oto wiadomość:

WE WER ELU CK YBECA USEOFT E NTH EFR EQUEN CYM ETH ODM EEDSLONGERCIPHERTEXT. (Mieliśmy szczęście, gdyż. często metoda częstości wymaga dłuższego kryptogramu.)

3.    THRPXDH

4.    SUCCESSATLAST (nareszcie sukces).

5.    AGENT 006 IS DEAD 007 (agent 006 nie żyje 007).

6.    Stwierdzasz, że istnieje 9 możliwych wartości a' i b': a' = 1,4,7,10,13,16, 19, 22, 25 i odpowiednio b' = 21, 6,18, 3,15,0,12,24, 9. Ponieważ nie masz żadnych dodatkowych informacji, po prostu sprawdzasz wszystkie te 9 możliwości; okazuje się, że tylko trzecia P s 7C + 18 (mod 27) daje tekst sensowny. Tekstami jawnymi odpowiadającymi tym dziewięciu przekształceniom są odpowiednio: „I DY IB RIF”, „I PS IH RIX", J AM IN RIO”, „I MG IT RIF”, „IYA IZ RIX”, J JV I£ RIO”,,J VPIK RIF”, „I GJ IQ RIX”, „I SD IW RIO”.

7.    (a) N; (b) Nę(N) = N¹ fi I! - — |; (c) 312,486,812,240.

PlW\ P1

8.    (a) Jeśli aź 1, to kongruencja (a - 1 )P = -b (mod N) ma dokładnie jed

no rozwiązanie w ciele F_v = L/NL.

(b)    P = 0 jest zawsze punktem stałym; dla N parzystych (wtedy liczba a musi być nieparzysta) kongruencja (a - \)P = 0 (mod N) ma co najmniej dwa rozwiązania P = 0 i P = N/2.

(c)    Każdy przykład, w którym liczba W jest parzysta i b nieparzysta; ogólniej, każdy przykład, w którym liczba b nie jest podzielna przez NWD(a -1, N).

10.    (a) a' = 435, b' = 64; „FOUNDTHEGOLD” (znalazłem złoto);

(b) a = 115, b = 76, „AWOFUWAE”.

11.    (a) Nie można wyznaczyć klucza z pierwszych dwóch kongruencji; ale odjęcie trzeciej od pierwszej daje 139a' = 247 (mod 900) i wtedy ó! = 73, b' = 768; „ARE YOU JOKING?” (czyżbyś żartował?); (b) a = 37, b = 384; „FWU ORI DCCUVGA

12.    „CCCP”, co jest rosyjskim skrótem ZSRR (Związek Socjalistycznych Republik Radzieckich).

13.    P = 37P + 384 (mod 900), co upraszcza się do 3P s 43 (mod 75); nie ma punktów stałych.