17011 Str135

264 Odpowiedzi do ćwiczeń

4.3

1.    (a) 24, 30, II, 13; (b) I, a² + 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_₂ - (1 — aj.    obliczamy lewą stronę (*)j modulo V w następu

jący sposób: jest ona równa a_j_₁gjt{, więc przystaje do

(1-3'

sl+3^

^{x_l.₂)gji~iⁱ modulo 3^J; wtedy pokazujemy, że (1 + 3)³'“^,Jti-» s

(mod 3') (korzystamy ze wzoru dwumianowego Newto

na). Zatem lewa strona (*)J przystaje do 1 — jc/_₂ 3^2U~^1}, a więc do 1 modulo 3^J. 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(a²) operacji na bitach, a więc cały algorytm wymaga 0(a³) operacji na bitach.

3. (a) Aby łatwiej obliczyć (g^b)^a w ciele F₃₁a, skorzystaj z tego, że (c + di)³² = c² + d^z\ otrzymasz A + Bi = 26 + 28/; (b) 20+13/; (c) P s 6C + 18 (mod 31); (d) YOU’RE JOK1NG! (żartujesz!).

4.    (a) K_e = 1951280, resztą z dzielenia przez 26⁴ jest 7 • 26³ + 0 • 26² + + 13 -26 + 6; jednak musisz dodać 1, by otrzymać macierz odwracalną

;(b)

DONOTPAY (nie płać).

5.    Funkcje f_A muszą być ze sobą przemienne, tzn. f_A f_B = f_Bf_A 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 f_A na podstawie znajomości pary (P, f_A (?)). Na przykład przesunięcie f_A(P) = P + b lub przekształcenie liniowe f_A(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 g^xa s 1 (mod p). Niech /= 2* i x = x₀ + 2jc_x + ... + + 2}~ⁱx_l__v Przyjmij gj = g^v mod p i = g^Xo+2jc,+*^,+2'"‘*'-^,a mod p (gdzie jako a_Q bierzemy a). W y-tym kroku oblicz aj-~i — ± 1 i przyjmij ^xj-i — 0, jeśli otrzymasz +1, i x_J__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* * y^rr* = g^ar*^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 = y_Al 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"⁺¹ — l)/(p — 1) «p". Liczba iloczynów stopnia mniejszego niż « może być pominięta. Liczba n_f nierozkladalayćh wielomianów stop*

1    pi

nia f wynosi — (p^f —    £ cfn_d) 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 = £ i_dd (i_d 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 pⁿ\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.