Str031 (2)

58

o tym prwkonnć, zauważmy. *c dla każdego d\ joAli bodziemy wielokrotnie podstawiać ,V^f* w miejsce A* w równaniu X^p4 ** X, to wreszcie otrzymamy .V'/”"'    ,\). W ten sposób udowodniliśmy:

Twierdzenie 2.1.7. Podciałami ciała F_p, są ciała l'_r- dla d będących dzielnikami/. Mli do ciała F, dołączymy element ciała Ty, to otrzymamy jedno z tych podciął.

Teraz już łatwo udowodnić wzór przydatny do obliczenia liczby wielomianów nicrozkładalnych danego stopnia.

Twierdzenie 2.1.8. Dla dowolnego ą = p* wielomian \⁹ — X rozkłada się tv pierścieniu F_r|A ] na iloczyn wszystkich unormowanych wielomianów nicrozkładalnych stopni d będących dzielnikami f.

Dowód. Jeśli dołączymy do ciała F_p pierwiastek a unormowanego wielomianu nicrozkładalnego stopnia d\/ to otrzymamy kopię izomorficzną ciała ly* która jest zawarta w F_p/. Ponieważ ot jest wtedy pierwiastkiem równania X^q - X - 0, więc ten unormowany wielomian nierozkładalny jest dzielnikiem X⁹ - X. Na odwrót, niech f(X) będzie unormowanym wielomianem nieroz-kładalnym będącym dzielnikiem wielomianu X⁹ — X. Wtedy f(X) musi mieć pierwiastki w (gdyż w tym ciele znajdują się wszystkie pierwiastki wielomianu X⁹ - X). Zatem/(X) musi mieć stopień będący dzielnikiem/, gdyż na podstawie twierdzenia 2.1.7 dołączenie pierwiastka daje podciało ciała F_ł. A więc unormowane wielomiany nicrozkładalne będące dzielnikami wielomianu X⁹ - X są to dokładnie wszystkie takie wielomiany, stopni będących dzielnikami / Ponieważ widzieliśmy już, że wielomian X⁹ - X nie ma pierwiastków wielokrotnych, więc wielomian X⁹ - X jest równy iloczynowi wszystkich takich wielomianów nierozkładalnych, czego należało dowieść.

Wniosek. Jeśli f jest liczbą pierwszą, to w pierścieniu F_p[A^r] istnieje (p* — p)l f różnych unormowanych wielomianów nierozkładalnych stopnia f

Zauważmy, że liczba (p* — p)l f jest całkowita, gdyż z małego twierdzenia Fermata dla liczby pierwszej f wynika, żtp^f = p (mod /). Aby udowodnić wniosek, oznaczmy przez n liczbę unormowanych wielomianów nierozkładalnych stopnia f. Zgodnie z twierdzeniem wielomian X^p/ — X, stopnia p^, jest iloczynem n wielomianów stopnia f i p nicrozkładalnych wielomianów pierwszego stopnia postaci X - a dla ae¥_p. Zatem porównanie stopni daje: p^f * nf + />, skąd wynika żądana równość.

Ogólnie, przypuśćmy, że liczba / nie jest pierwsza. Wtedy niech n_A oznacza liczbę unormowanych wielomianów nierozkładalnych stopnia </, o współczynnikach z ciała F_p. Wtedy mamy równość n_f— (p^f — Y,dn_d)!f gdzie sumowanie rozciąga się na wszystkie d < f będące dzielnikami /.

Uogólnimy teraz oszacowania czasu z rozdziału 1, z arytmetyki modulo p na działania w dowolnych ciałach skończonych.

Twierdzenie 2.1.9. Niech F. bfdiit dałam skoóczonym, gdzie tf -^r p^, oraz niech F(X) będzie wielomianem nlerozkladalnym stopnia / o współczynnikach z ciała V . Wtedy mnożenie lub dzielenie dwóch elementów dala V_ą może być wykonane za pomocą 0(log^ł<y) operacji na bitach. Je.ili k jest liczba całkowitą dodatnią, to element dala V_ą może być podniesiony do k-tej pateyi za pomocą Oflog k log¹4) operacji na bilach.

Dowód. Element ciała F_f jest wielomianem o współczynnikach z V_p ~ Z/pZ, wziętym modulo F(X). Aby pomnożyć dwa takie elementy, musimy pomnożyć wielomiany - to wymaga 0(f²) mnożeń liczb całkowitych modulo p (oraz pewnej liczby dodawań modulo /?, które zajmują znacznie mniej czatuj - a następnie podzielić iloczyn przez wielomian F(X) i jako wynik wziąć resztę. Dzielenie wielomianów wymaga O(f) dzieleń liczb całkowitych modulo p oraz 0(f²) mnożeń liczb całkowitych modulo p. Ponieważ mnożenie modulo p wymaga O (log²/?) operacji na bitach i dzielenie (np. z wykorzystaniem algorytmu Euklidesa) wymaga O (log³/?) operacji na bitach (por. wniosek do twierdzenia 1.2.2), więc całkowita liczba operacji na bitach wynosi: 0(/²log²p -j-/log³/?) = 0((f\ogp)³) - 0(log³^r). Aby udowodnić teraz podobną równość dla dzielenia, wystarczy pokazać, że element odwrotny można znaleźć w czasie 0(log³q). Korzystając z algorytmu Euklidesa dla wielomianów o współczynnikach z F_p (por. ćwiczenie 9 z podrozdziału 1.2), musimy zapisać 1 jako kombinację liniową naszego elementu dała F_f (tzn. danego wielomianu stopnia < /) i ustalonego wielomianu F(X) stopnia /To wymaga O(f) dzieleń wielomianów stopni mniejszych od / i każde takie dzielenie wymaga 0(/²log²p + /log³/?) = 0(f²log³p) operacji na bitach. Zatem całkowity czas potrzebny do znalezienia elementu odwrotnego wynosi 0(f³log³p) = = 0(log³#). Wreszcie, k-ta potęga może być obliczona za pomocą algorytmu iterowanego podnoszenia do kwadratu w taki sam sposób jak w przypadku działań modulo m (por. koniec podrozdziału 1.3). To wymaga Oflogk) mnożeń (lub podnoszenia do kwadratu) elementów dała F₄, a zatem wymaga 0(logklog³?) operacji na bitach. To kończy dowód.

Zakończymy ten podrozdział przykładem obliczeń wykonanych na wielomianach nad dałem skończonym. Pokażemy je na przykładzie najmniejszego (i być może najważniejszego) ciała skończonego, mianowide dwuelementowe-go ciała F₂ = {0,1}. Wielomian z pierścienia F₂[Af] jest po prostu sumą potęg zmiennej X. W pewnym sensie wielomiany nad ciałem F, przypominają liczby całkowite zapisane w systemie pozycyjnym o podstawie p, gdzie cyfry rozwinięcia odpowiadają współczynnikom wielomianu. Liczba zapisana na przykład w systemie dwójkowym jest sumą potęg 2 (ze współczynnikami 0 lub 1), dokładnie tak, jak wielomian nad F₂ jest sumą potęg X. Ale to porównanie często zawodzi. Na przykład suma dowolnie wielu wielomianów stopnia z/jest wielomianem stopnia (co najwyżej) d\ podczas gdy suma wielu ^-cyfrowych liczb całkowitych jest liczbą całkowitą mającą więcej niż d cyfr dwójkowych.

Wyszukiwarka

Podobne podstrony:
Str031 (2) 2 nulu dkflńcrflne I reszly kwadratowi?58 o tym prwkonnć, zauważmy. *c dla każdego d joAl
w kwadraty zawarte w tym wielokącie. Udowodnić, że jeśli wartości dowolnych dwóch przystających
58 KWIATEK Z KWADRACIKAMI 58 Różne ozdoby 2 rurki skośnie ścięte 6 średnich muszelek (płatki kwiatka
skanuj0016 166 Magdalena Podsiadło Praca nad tym filmem była dla twórcy bardzo mało satysfakcjonując
skanuj0099 (10) 202 AKSJOLOGIA ETYCZNA ukazują podmiotowi odpowiadającą mu formę doskonałości - i w
skanuj0335 (2) 350 PHP i MySQL dla każdego już indeks związany w tym kluczem. Z tego samego względu
SNV36276 . się ojczyźnie. A także o tym, że najdotkliwszą dla króla przykrością HaJll losu, oddziela
img199 199 Zajmiemy się obecnie analizą widmową sygnału (1.5.12). M tym celu obliczamy dla niego uśr

więcej podobnych podstron