Str131
?>56 Odpowiedź do MewA
|9. n » 3; p - I - 25 • 65; r m a*y •» 201 (mod p) (obliczamy 302s* 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 / *= 2a, 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 v2 = a (mod pB_ 1). Aby znaleźć ostatnią cyfrę V, , e{0, I, .... p — 1} liczby .v = j? + xa_,p“_I, przyjmijmy j?a - a + bp*~1 dla pewnej liczby b i wykonajmy następujące obliczenia modulo p“: x2 - (X + x^lp*~1)2 s Z1 -|- 2x0xa„lp*~l =
= a + p*~l(b -f 2.v0a'o„ ,). Wystarczy zatem, by xa_i s —(2x0)~lb (mod p) (zauważ, że 2x0 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 b2 i blb2, to po podzieleniu obu kóńgrucncji stronami otrzymalibyśmy relację (*) dla b2 (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 p2|». Wtedy (—)= 1, ale
bJ = 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 nje może przystawać do —1 modulo n/p, a więc tym bardziej modulo n. Następnie niech a1 będzie dowolną nieresztą kwadratową modulo p i niech a2 = 1. Skorzystaj z chińskiego twierdzenia o resztach, by znaleźć rozwiązanie b układu kongruencji x = al (mod p), x = a2 (mod nip).
22. b1 = (/ + oc)p(ł + a) = (/ + ap)(/ + a) = (t - a)(t -f a) = f2 — a2 = 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 Fp, 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|ó2 + 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) = N1 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 Fv = 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.
Wyszukiwarka
Podobne podstrony:
mat odp004 307 Odpowiedzi do zadań 2.25 a) y(t) — Ce 4 + C2e2t — -eł + -e 24; b) y
pogoda kolorowanka (25) Wytnij rysunki z symbolami pogody i przeklej je obok dzieci ubranych odpow
Matem Finansowa$1 Odpowiedzi do zadań i testów 241 25. 26. 27. 28. 29. a) i,2) <19,62%; &nb
22903 PTDC0066 (2) Odpowiedzi do zadań 4 l 1. ** = 4800, ** = 7000, F(*f,*?) = 25
Konstytucyjny system organów państwowych - 25 listopada 2009 Referendum jest, odpowiednio do wspólno
Strona0079 792.13. Odpowiedzi do zadań z drgań bryły 54 k - n _i „ 2tt -= 1,9 s ,
lastscan118 Odpowiedzi do zadań I Rozdział 1 1.1. 16.25%. 1.2. a
226 (30) nia się odpowiednio do zmiany prędkości dźwięku — zgodnie z równaniem (25), tzn. j du —--——
25 (224) ISTQB Advanced Level - Test Manager sample exam - version 2012Pytanie 25 z 65 &
skanuj0015 /- V ___- - + ★ Wpisz odpowiednio do tabelki wyrazy z
więcej podobnych podstron