Str128

252 Odpowiedzi do ćwiczeń

252 Odpowiedzi do ćwiczeń

5. 3 dla r/ I: A', X± I; 3 dla rf=2: X¹ -I- I, X¹ ± X~ 1; 8 dla    3; A'³ !• X⁷ I (X - I), A'³ - V^? -I;(X + I), A'³ ± (X² - I), X*-X± ]• 18 dla </« 4; 48 dla d = 5; 116 dla 6.

6.    (p^r

7.    (a)    - 1 = A V i (A’ + 1)/; (b) //TO = A'³ + X² + 1 =/+ (A'² +

+ AIj?; (C) NWD = 1 = (A' - 1)/- (A'² - A^r + l)g; (d) NWD = AT + 1 =

» (-V - I)/- (A*³ - A*² + 1 )g; (c) NWD = AT + 78 = (50AT+ 20)/+

+ (51 A'³ + 26A'² + 27AT + 4)g.

8.    Ponieważ NWD(f, /') = A'² + 1, więc pierwiastkami wielokrotnymi są ±a², gdzie a jest generatorem grupy FJ wskazanym w tekście książki.

9.    (a) Podnosząc 0 = a² + 6a + c do potęgi p i korzystając z tego, że b^p = b

i c^p = c. otrzymujemy 0 = (a*)² + 6a^p + c.

(b)    Dwoma różnymi pierwiastkami tego wielomianu są wtedy a i a^p. Wtedy a jest elementem przeciwnym do sumy tych pierwiastków i b jest iloczynem tych pierwiastków.

(c)    (ca + d)^p+1 = (ca^p + d)(ca + d) i wystarczy wymnożyć prawą stronę i skorzystać z (b).

(d)    (2 + 3/)^5(l9+1)+1 = (2² + 3²)⁵(2 + 31) = 14(2 + 3/) = 9 + 4i

10.    W każdym dzieleniu wielomianów (najpierw/przez g, a potem rj przez fj+i) najpierw musimy znaleźć element odwrotny modulo p do współczynnika przy najwyższej potędze zmiennej w r_J+i (co wymaga 0(log³p) operacji na bitach), a następnie musimy wykonać 0(d²) mnożeń elementów ciała (czyli mnożeń liczb modulo p), wymagających po 0(log²p) operacji na bitach. Zatem każde dzielenie wymaga D(log³p + d²\og²p) operacji na bitach, czyli wykonanie całego algorytmu Euklidesa wymaga 0{d) • 0( log²/? (log/? + d¹)) = 0(dlog²/?(log/? + d²)) operacji. (To wyrażenie można uprościć do 0(dlog³/?), jeśli założymy, że d nie rośnie szybciej niż >/log/?, i do 0(d²\og²p)_i jeśli założymy, że p nie rośnie szybciej niż e^il.)

11.    (a) Niech a będzie pierwiastkiem równania X² + X + 1 = 0; wtedy tymi

trzema kolejnymi potęgami a są a, a + 1 i 1.

(b)    Niech a będzie pierwiastkiem równania X² + X + 1 = 0; wtedy tymi siedmioma kolejnymi potęgami a są a, a², a + 1, a² + a, a² + a + 1, a² +1,1.

(c)    Niech a będzie pierwiastkiem równania X² — X — 1 = 0; wtedy 26 kolejnych potęg a to: a, a², a + 1, a² + a, a² + a + 1, a² — a + 1, —a² — a + 1, —a² — 1, —a + 1, —a² + a, a² — a — 1, —a² + 1, —1, po których następuje 13 takich samych elementów, w których jednak wszystkie znaki + i — są zamienione.

(d)    Niech a będzie pierwiastkiem równania X² — X + 2 = 0; wtedy 24 kolejne potęgi a to: a, a — 2, —a — 2, 2a + 2, — a + 1, 2, po których następuje 6 takich samych elementów pomnożonych przez 2, potem 6 pomnożonych przez -1, wreszcie 6 pomnożonych przez —2, co łącznie daje 24 potęgi a.

12.    gdyż dla każdej /, Ó(2^| potęg elementu * musimy pomnożyć poprzednie wyrażenie przez «i, jeśli wystąpi i/_# musimy dodać wielomian niższego stopnia równy d do wyniku (czyli do poprzedniego wyrażenia, w którym wszystkie potęgi a zostały zwiększone o 1); to wszystko wymaga jedynie £>(/) operacji na bitach.

13.    (a) p = 2 i 2⁷ - I jest liczbą pierwszą Mersennc'a (por. przykład 1 i ćwiczenie 2 z podrozdziału 1.4); (b) oprócz przypadków wspomnianych w (a) również wtedy, gdy p = 3 i gdy (3^ - l)/2 jest liczbą pierwszą (tak jak w (a) wymaga to, by sama liczba / była pierwsza, ale nie jest to wystarczające, jak pokazuje przykład/= 5) oraz gdy p jest postaci lp' + 1, gdzie p' jest liczbą pierwszą i/= 1. Niestety nie wiadomo, czy istnieje nieskończenie wiele ciał prostych spełniających któryś z warunków wymienionych w (a) i (b) (chociaż przypuszcza się, że tak jest). Liczby pierwsze p\ dla których liczba p = 2p^f + 1 jest też pierwsza, są nazywane liczbami pierwszymi Germain, od nazwiska Sophie Germain, która w 1823 roku udowodniła tzw. pierwszy przypadek wielkiego twierdzenia Fermata dla wykładników tej postaci.

14.    Wybierzmy ciąg n_}, dla którego ?(»/)/»;-*0 gdy;-* x (por. ćwiczenie 23 z podrozdziału 1.3) i taki, że żadna liczba n_} nie jest podzielna przez p, oraz niech będzie rzędem p modulo rij (czyli najmniejszym wykładnikiem potęgi liczby p przystającej do 1 modulo nj).

15.    Wszystkie wielomiany, w których Xⁱ występuje ze współczynnikiem nieze-rowym wtedy i tylko wtedy, gdy p\j.

16.    Sprowadź zadanie do przypadku, gdy ; = d, pokazując, że jeśli <J^j(a) = a i o^f(a) = o, to aⁱ(a) = a (por. dowód twierdzenia 1.4.2). Zauważ, że ciało Fpd, które jest ciałem rozkładu wielomianu X^pd - X, jest zawarte w F_|f gdyż każdy pierwiastek a tego wielomianu jest również pierwiastkiem wielomianu X^ą — X (aby się o tym przekonać, podnieś ffd razy obie strony równości a^p = a do potęgi p^d).

17.    Udowodnij, że b ' = b^{pH~^L)l(pd~^l) jest elementem dała wykazując, że jest to punkt stały przekształcenia <r^d (tżn. przekształcenia polegającego na podnoszeniu do potęgi p*)\ udowodnij następnie, że jest to generator grupy multyplikatywnej tego ciała, wykazując, że wszystkie potęgi (ó')^J dla j = 0, p^d — 2 są różne (wynika to z tego, że potęgi b* dla ; = 1, ...» pⁿ — 1 są różne).

2.2

1.    Zbiorami reszt kwadratowych są: dla p = 3, {1}; dla p = 5, {1, 4); dla

p = 7, {1,2,4}; dlap = 13, {1,3,4,9,10,12}; dla/> = 17, {1,2,4,8,9,13, 15, 16}; dla p = 19, {1, 4, 5, 6, 7, 9, 11,16, 17}.    , ₂ v

2.    (b) Z (a) i twierdzeń 2.2.2 oraz 2.2.4 wynika, że (--) =1=2^

(mod p). To oznacza, że    s -1 (mod p) dla pewnego l> 2.