17011 Str135
264 Odpowiedzi do ćwiczeń
4.3
1. (a) 24, 30, II, 13; (b) I, a2 + et, o, a + 1.
2. (i) Aby uzasadnić przeniesienie a na lewą stronę, zauważ, że jeśli * < ą>(3“)
jest rozwiązaniem kongrucncji 2'fl 1 (mod 3“), to r/>(3“) — x jest rozwiązaniem wyjściowej kongrucncji. Jeśli a = 2 (mod 3), to rozwiązujemy kongrucncję 2*(2o) = 1 (mod 3"), w której mamy 2a s 1 (mod 3) i wtedy x -f I jest rozwiązaniem wyjściowej kongrucncji. Jeśli a s 1 (mod 3), to rozwiązanie x musi być liczbą parzystą, gdyż nieparzyste potęgi dwójki przystają do 2 modulo 3. (iii) Aby pokazać, że zachodzi (*)j po wybraniu Xj_2 - (1 — aj. obliczamy lewą stronę (*)j modulo V w następu
jący sposób: jest ona równa aj_1gjt{, więc przystaje do
(1-3'
sl+3^
{xl.2)gji~ii modulo 3J; wtedy pokazujemy, że (1 + 3)3'“,Jti-» s
(mod 3') (korzystamy ze wzoru dwumianowego Newto
na). Zatem lewa strona (*)J przystaje do 1 — jc/_2 32U~1}, a więc do 1 modulo 3J. Wreszcie, aby oszacować liczbę operacji na bitach, zauważmy, że za każdym razem, gdy wykonujemy krok (iii), wykonujemy kilka mnożeń i kilka redukcji modulo (czyli dzieleń) liczb mających 0(a) bitów. Zatem każdy krok wymaga 0(a2) operacji na bitach, a więc cały algorytm wymaga 0(a3) operacji na bitach.
3. (a) Aby łatwiej obliczyć (gb)a w ciele F31a, skorzystaj z tego, że (c + di)32 = c2 + dz\ otrzymasz A + Bi = 26 + 28/; (b) 20+13/; (c) P s 6C + 18 (mod 31); (d) YOU’RE JOK1NG! (żartujesz!).
4. (a) Ke = 1951280, resztą z dzielenia przez 264 jest 7 • 263 + 0 • 262 + + 13 -26 + 6; jednak musisz dodać 1, by otrzymać macierz odwracalną
;(b)
DONOTPAY (nie płać).
5. Funkcje fA muszą być ze sobą przemienne, tzn. fA fB = fBfA dla wszystkich par użytkowników A i B\ musisz wykorzystać to wraz z dobrym systemem potwierdzania tożsamości (tak jak jest to wyjaśnione w tekście). Nie może przy tym istnieć łatwa metoda znajdowania klucza dla fA na podstawie znajomości pary (P, fA (?)). Na przykład przesunięcie fA(P) = P + b lub przekształcenie liniowe fA(P) = aP ma pierwszą własność, ale nie ma drugiej, gdyż znajomość jednej pary (P, P + b) (lub (P, aP)) umożliwia natychmiastowe znalezienie b (lub a). Przykład opisany w tekście ma te własności, gdyż założyliśmy, że problem logarytmu dyskretnego nie może być rozwiązany w rozsądnym czasie.
6. P = 6229 = „GO!” (idź!).
7. (a) Najpierw zastąp x przez p - 1 - x tak, by przejść do kongruencji równoważnej gxa s 1 (mod p). Niech /= 2* i x = x0 + 2jcx + ... + + 2}~ixl_v Przyjmij gj = gv mod p i = gXo+2jc,+*,+2'"‘*'-,a mod p (gdzie jako aQ bierzemy a). W y-tym kroku oblicz aj-~i — ± 1 i przyjmij xj-i — 0, jeśli otrzymasz +1, i xJ_i = 1, jeśli otrzymasz —1; obliczasz
także %j *» gf , i Oj ~ g'f‘ y. JeMi / •» /, to algorytm jest zakończony, (b) <5(logV). (c> fc = 7912.
8. rHEYREFUSHOURTERMS (odrzucają nawę warunki).
9. Aby znaleźć x, Alicja doprowadza kongruencje g* * yrr* = gar*ka do postaci fi? s ar -h fejc (mod p — I) i otrzymuje rozwiązanie x# k"ł(S“ flf) (mod p — 1). Bolek zna p, g i y = yAl a wiec może sprawdzić, że g* =
(mod p), gdy tylko otrzyma parę (r, x) i S. Wreszcie, ktoś, kto potrafi rozwiązać problem logarytmu dyskretnego, potrafi wyznaczyć a z g i y, a więc potrafi podrobić podpis, znajdując x.
10. 107.
11. (a) 9/128 = 7,03%, 160/1023 = 15,64%; (b) 70/2187 = 3,20%,
1805/29524 = 6,11%. (Por. wniosek do twierdzenia 2.1.8.)
12. (a) Pomiń wszystkie wyrazy oprócz zawierającego najwyższą potęgę p.
Wtedy liczba wielomianów unormowanych wynosi (p"+1 — l)/(p — 1) «p". Liczba iloczynów stopnia mniejszego niż « może być pominięta. Liczba nf nierozkladalayćh wielomianów stop*
1 pi
nia f wynosi — (pf — £ cfnd) as ——. Liczba iloczynów stopnia
J d<f.*\f f
n jest więc równa następującej sumie, gdzie sumowanie rozciąga się na
m
wszystkie podziały n = £ idd (id 5= 0):
4=1
Zatem
Zatem
Jest to oczywiście liczba dodatnia; aby przekonać się, że P(n, ni) < 1, wystarczy zauważyć, że istnieje w przybliżeniu pn\n unormowanych wielomianów nierozkładalnych stopnia n, a więc prawdopodobieństwo tego, że wielomian unormowany nie ma żądanego rozkładu, wynosi co najmniej 1/n.
(c) P(3, 2) = 2/3, P(4, 2) = 5/12, P(5, 2) =13/60, P(6, 2) =19/180,
i+ 2j=n, 0 < l,J
P(7, 2) = 29/630.
4.4
1. (a) tak, 1; (b) tak, 0; (c) nie, 2; (d) nie, 0; (e) tak, 1; (f) nie, 1.
2. (a) Zastosuj indukcję względem k.
(b) Aby dowieść drugiej części, niech u, będzie ostro większa od 1 + «!-!+ ... + i>o i przyjmij K = u,_l.
Wyszukiwarka
Podobne podstrony:
20319 Str124 Odpowiedzi do ćwiczeń1.1 i. (112111)3.2- (26° ii) 3. 10001100101; 1101 IT 1010 1011 WE
Protok?? Protokół pomiarowy do ćwiczenia nr 30 tl z dnia 20ńdl OŚ M] Wielkość (symbol) ■x i L i i
MODUŁ IIIMATERIAŁ POMOCNICZY NR 2 ODPOWIEDZI DO ĆWICZEŃ Ćwiczenie I szczoteczka do zębów, grzebień,
Odpowiedzi do ćwiczeń Planeta Nowa 2 -wysoka wartość BKP na jednego mnieszkańca -produkcja rolna
Odpowiedzi do ćwiczeń Planeta Nowa 2 -wysoka wartość BKP na jednego mnieszkańca -produkcja rolna
78698 P1060878 (2) natywnych odpowiedziKlucz do ćwiczeń to w 13.2.2.2. Ułóż larf B2 i B3. Sprawdź,&n
MODUŁ III MATERIAŁ POMOCNICZY NR 2 ODPOWIEDZI DO ĆWICZEŃ Ćwiczenie 1 szczoteczka do zębów, grzebień,
anna paszkowska rogacz strona6 107 -Załączniki do ćwiczeń __ 24. Sukces w życiu oznacza dla mnie u
Str128 252 Odpowiedzi do ćwiczeń 252 Odpowiedzi do ćwiczeń 5. 3 dla r/ I: A , X± I; 3 dla rf=2: X1 -
więcej podobnych podstron