69654 Str032 (2)

60 2 Cinhi Rkortc?onc i rcfi/ty kwadratowe

Przykład 3. Niech/(A⁴) * A⁴ + A'³ + AT¹ +1, g(X) - A’³ + I e F₂[A^r]. Znajdź-my NWD(f g) za pomocą algorytmu Euklidesa dla wielomianów i przedstawmy ten największy wspólny dzielnik w postaci u(X)f(X) -F v(X)g(X).

Rozwiązanie. Kolejne dzielenie wielomianów daje nam poniższy ciąg równości, które prowadzą do wniosku, że    g) = X -f 1. Tc równości, wykorzys

tywane od końca, pozwalają nam przedstawić X -l- 1 jako kombinację liniową fig, (Zauważ, przy okazji, że w ciele charakterystyki 2 dodawanie jest tym samym działaniem co odejmowanie, tzn. a — b = a + b — 2b = a + b.) A oto obliczenia:

/=(A'+l)* + (A'^l + A') j = (A'+l)(X² + A0 + (r+l)

Jr*+*>*(?+1)

i stąd

X+ 1 =* + (A'+ 1)(AT²+A0=_ff+(X+ !)(/•+(AT+ 1)») = (JT+1 )f+[X¹)g. Ćwiczenia

1.    Dla p = 2,3,5,7,11,13 i 17 znajdź najmniejszą dodatnią liczbę całkowitą, która generuje grupę FJ, i określ, ile jest generatorów wśród liczb 1, 2, 3,1.

2.    Niech (Z/p^aZ)* oznacza zbiór wszystkich reszt modulo /?“ mających elementy odwrotne, tzn. takich, które nie są podzielne przez p.

Ostrzeżenie: Nie pomyl zbioru Z//?*Z (który ma/-/"¹ elementów odwracalnych) ze zbiorem F_p« (w którym wszystkie elementy prócz 0 są odwracalne). Oba te zbiory są równe tylko dla a = 1.

(a)    Niech g będzie liczbą całkowitą, która generuje grupę EJ, gdzie p > 2. Niech a będzie dowolną liczbą całkowitą, większą od 1. Udowodnij, że albo g, albo {p + l)g generuje (Z//?“Z)*. Zatem ta grupa jest też grupą cykliczną.

(b)    Udowodnij, że jeśli a > 2, to grupa (Z/2“Z)* nie jest cykliczna, ale liczba 5 generuje podgrupę zawierającą połowę elementów całej grupy, mianowicie te liczby, które przystają do 1 modulo 4.

3.    Ile elementów zawiera najmniejsze rozszerzenie ciała F_s zawierające wszystkie pierwiastki wielomianów X² + X +\ i X* + X 1?

4.    Dla każdej liczby d < 6 znajdź liczbę wielomianów nierozkładalnych stopnia d nad ciałem F₂ i wypisz je wszystkie.

5.    Dla każdej liczby d < 6 znajdź liczbę unormowanych wielomianów nierozkładalnych stopnia d nad ciałem F₃ i dla d < 3 wypisz je wszystkie.

6.    Niech / będzie potęgą liczby pierwszej p. Znajdź prosty wzór wyrażający liczbę unormowanych wielomianów nierozkładalnych stopnia / nad ciałem |g

7.    W każdym z poniższych przykładów znajdź NWD( f g) dla f g^pFJX] za pomocą algorytmu Euklidesa dla wielomianów (por. ćwiczenie 9 do podrozdziału 1.2). W każdym przypadku przedstaw największy wspólny dzielnik w postaci kombinacji liniowej fi g, tzn. w postaci d(X) = u(X) f(X) + + v(X)g(X).

Wf=X³ + X+),g = X² + X+\,p = 2-

(b)    f= X⁶ -t- X⁵ + X* + X³ + X² + X + 1, g = X* + X² + X + Up- 2;

(c) /=X³~X-l-l,g = X² + i,p=:3;

(d) f=X⁵ + X* + X³-X²-X+l,g = X³ + X² + X+ \,p=3;

(e)    /= A'⁵ + 88Af⁴ + 73J³ + 83*² + 51X+ 67, g=X³ + 97X* + 40X+ 38, />= 101.

8.    Obliczając NWD(f f) (por. ćwiczenie 10 do podrozdziału 1.2), znajdź wszystkie pierwiastki wielokrotne wielomianu f(X) = X¹ + X⁵ + X^A — -X³ — X²-X+le F₃[A'] w jego ciele rozkładu.

9.    Niech aeF_pJ będzie pierwiastkiem wielomianu X² + aX + b, gdzie a, beF_p.

(a)    Udowodnij, że a^p też jest pierwiastkiem tego wielomianu.

(b)    Udowodnij, że jeśli a^F_p, to a = -a - i^p i b - a'*¹.

(c)    Udowodnij, że jeśli a$łF_p i c, de F_p, to {cz +dy*² = d² - acd+bc² (a więc eF_p).

(d)    Niech z będzie pierwiastkiem kwadratowym z — 1 w F₁₉j. Wykorzystaj punkt (c) do obliczenia (2 + 3/)¹⁰¹ (tzn. zapisz wynik w postaci a -f bi, a, be F₁₉).

10.    Niech d będzie większym ze stopni dwóch wielomianów f geF_p[X]. Oszacuj za pomocą d i p liczbę operacji na bitach potrzebnych do obliczenia NWD(f g) za pomocą algorytmu Euklidesa.

11.    Dla każdego z podanych ciał F₄, gdzie q = p^f, znajdź wielomian nieroz-kładalny o współczynnikach w ciele prostym, którego pierwiastek i jest pierwiastkiem pierwotnym (tzn. generuje grupę FJ), a następnie wypisz wszystkie potęgi a jako wielomiany zmiennej a, stopnia < /: (a) F₄; (b) F_g; (c)F₂₇;(d)F₂₃.

12.    Niech F{X)eF₂[X] będzie pierwotnym wielomianem nierozkładalnym stopnia f Oznacza to, że jeśli a jest pierwiastkiem F(X), to potęgi a wyczerpują całą grupę F*/. Wykorzystując notację O, oszacuj (za pomocą /) liczbę operacji na bitach potrzebnych do zapisania każdej potęgi a jako wielomianu zmiennej a, stopnia mniejszego niż /.

13.    (a) Jakie warunki muszą spełniać p if by każdy element F_p/, oprócz 0 i 1,

był generatorem grupy FJ/?

(b) Jakie warunki muszą być spełnione, by każdy element # 0,1 był albo generatorem, albo kwadratem generatora?

14.    Dla dowolnej liczby pierwszej p pokaż, że istnieje ciąg = p^fi potęg p takich, żc prawdopodobieństwo tego, że losowy element ciała F, jest generatorem FJ, dąży do 0, gdy co.

15.    Jakie wielomiany w FJX] mają pochodną równą tożsamośdowo zeru?