86049 Str143 (2)

280 Oriprwittfri do ćwjcrfń

(c)    Podwojonym punktem (v. y) jest (,r\ y⁴) (zauważ, że przekształcenie polegające na podnoszeniu do czwartej potęgi jest „przekształceniem Frobeniusa", tzn. generatorem grupy Galois F_4r nad F₄).

(d)    r-krotne podwojenie dowolnego punktu daje (x^A\ y⁴') = (je, y), czyli każdy punkt Pc E spełnia równanie 2^rP = P.

8.    (a) Skorzystaj z tego, te dany element ciała należy do F₂ wtedy i tylko

wtedy, gdy spełnia równanie x² = a; skorzystaj również z tego, że równość (a + ó)² = a² + ó² zachodzi w każdym ciele charakterystyki 2.

(b)    Przekształcenie z*-* z + 1 jest przekształceniem wzajemnie jednoznacznym między zbiorem tych z, które mają ślad 0, i zbiorem tych z, których ślad jest równy 1.

(c)    Wybierz losowy element x&F₂J podstaw wielomian x³ + ax + b zamiast z w g(z) i jeśli z = x* + ax + b jest jednym z 50% elementów mających ślad 0, to punkt (je, g{z)) leży na krzywej.

9.    Gdy mamy do czynienia z krzywą E modulo p, używamy tych samych wzorów (4) i (5) z podrozdziału 6.1. Jeśli dodajemy dwie mniejsze wielokrotności kP - k_lP + k₂P, to otrzymamy punkt w nieskończoności wtedy, gdy mają one (po zredukowaniu modulo p) te same współrzędne x i przeciwne współrzędne y. Jest to równoważne warunkom (1) i (2) w ćwiczeniu.

10.    Mianownik w 8P jest podzielny przez p = 23, a więc P mod 23 ma rząd 8 w grupie E mod 23 na podstawie ćwiczenia 9. Jednak z twierdzenia Hassego wynika, że krzywa E mod 23 ma więcej niż 8 punktów.

11.    (676,182), (385, 703); (595,454), (212,625); (261, 87), (77, 369); (126,100), (66, 589); (551, 606), (501, 530); (97, 91), (733, 110); (63, 313), (380, 530).

63

1. (a) 1 - 1 lq\ (b) 1 - 1 fa.

3. (a) Jeśli n = 2^2ft + 1 jest liczbą pierwszą, to dowolna liczba a taka, że

j s — 1, ma tę własność. Porównaj ćwiczenie 15 z podrozdziału 2.2

w przypadku a = 3,5,7. Natomiast jeśli p jest właściwym dzielnikiem pierwszym liczby n i jeśli a²³    = — 1, to liczba 2^2k jest wielokrotno

ścią rzędu a modulo p, ale 2^{zk ł} nie jest, tzn. ten rząd jest równy 2^2k = n — 1 > p — 1, co jest niemożliwe.

(b) Po pierwsze załóżmy, że n = 2^P — 1 jest liczbą pierwszą. Aby pokazać, że E mod n ma 2^P punktów, zob. ćwiczenie 7(a) z podrozdziału 6.1. Aby pokazać, że ta grupa jest cykliczna, udowodnij, że są tylko dwa punkty rzędu 2, ponieważ wielomian trzeciego stopnia x* + x ma tylko jeden pierwiastek modulo n. Wtedy dowolny z 50% punktów, które generują E mod n (tzn. które nie są podwojeniami żadnego punktu

w E mod /i), ma własności ())-(2y. Na odwrót, zał/iimy, że n roa wfafc-ciwy dzielnik pierwszy /, Gdyby punkt /'miał własności CI)-{2), to r/ąd P na /T mod / byłby dzielnikiem 2', ak ⁿ** 2* ' tzn byłby równy 2*. Ale wtedy liczba 2* — « -f I byłaby dzielnikiem liczby punktów E mod /, co przeczy twierdzeniu Hassego, które mówi, źe ta liczba jest mniejsza niż / + 2y/l + 1.

Aby wygenerować losowe punkty E mod l, wybierz losowo xeTL}n'A. Jeśli okaże się, że b = x³ + x jest kwadratem modulo n, to przyjmując >> = ó⁽ⁿ⁺I)/4, otrzymamy y² — b * ń** ^l>/2 * *⁵ -+■ x. CPor. uwagę I na końcu podrozdziału 2.2.)

6.4

1.    NWD(2^h — 1, n) = n, ale NfVD(3* - 1, n) = 127; « = 127 - 421.

2.    Prawdopodobieństwo tego, że dla losowego elementu aefZ/pZ)* mamy p\a^k — 1, wynosi NWJDQc, p — l)/(p— 1). Ponieważ jest tylko niewielka szansa na to, by liczba a* — 1 była podzielna przez jakiś inny dzielnik n, więc ten wzór daje również oszacowanie prawdopodobieństwa tego, źe NWD(a^k SI l,/i) = p.

3.    (a) 3/41; (b) 22/41; (c) 25/127; (d) 68/127; (e) 105/399.

4.    Wybierz k — 2⁶ • 3* • 5². Podamy teraz pierwszą wartość a, dla której ta metoda daje dzielnik, ten dzielnik oraz wartość k_lt dla której algorytm zatrzymuje się: (a) 1, 37, 2³; (b) 2, 71, 2⁶ • 3* - 5; (c) 1, 67, 2* - 3* • 5; (d) 1, 47, 2⁶ • 3; (e) 2, 79, 2⁶ * 3* • 5^Z; (f) 1, 73, 2⁶ - 3; (g) 5, 53, 2²; (h) 4, 59, 2⁶ • 3²; (i) 1, 47, 2⁶ • 3; 0 3, 97, 2⁶ • 3; (k) 1, 61, 2⁶ • 3* • 5².

5.    Gdyby zdarzyła się ta ostatnia możliwość, to mielibyśmy l^T{k_lJ[)P mod p— O mod p dla pewnej liczby i < /, podczas gdy (JcJTyP mod p # O mod p. Ale V jest iloczynem Hczb pierwszych /*<4a nasz wybór wykładników w (2) gwarantował, że dla każdej takiej liczby /* najwyższa potęga /*, która mogłaby dzielić rząd punktu P mod p w grupie E mod p, już wystąpiła w (/*)“*', tzn. w k_l/l.

6.    (a) Jeśli okaże się, że liczba n jest podzielna tylko przez liczby pierwsze

przystające do 3 modulo 4, to dla każdej takiej liczby p\rt krzywa E mod p będzie miała p 4- 1 punktów (por. ćwiczenie 7(a) z podrozdziału 6.1 w przypadku, gdy a = — 1; ale to samo rozumowanie stosuje się do dowolnego a). W takim przypadku umiana a nic nie pomoże, jeśli dla każdej liczby pierwszej p\n liczba p + 1 jest podzielna przez dużą liczbę pierwszą.

(b) Jeśli okaże się, że liczba n dzieli się tylko przez liczby pierwsze p przystające do 2 modulo 3, to zawsze krzywa będzie miała p + 1 punktów (por. ćwiczenie 7(b) z podrozdziału 6.1) i znów zmiana b nic nie porno-