Str026 (2)

48 I Kilka zagadnień elementarnej teorii licrh

wyznaczone jednoznacznie prze?, odpowiadające im ciągi r liczb i oszacuj liczbę operacji na bitach potrzebnych do znalezienia ciągu r liczb odpowiadających iloczynowi ab, jeśli masz dane ciągi r liczb odpowiadające liczbom a i b.

Bibliografia

1.    Hrillhnrt J., l.ehmer D.H., Sdfridgc S.L., Tuekerman B., Wagstaff S.S., Jr.: Factorizallons of b* ± 1, b = 2, 3, 5, 6, 7,10,11, 12, up to High Po wen. Amer. Maili. Socicty, 1983.

2.    Dick non L.E.: Hisiory of ihc Theory af Numbers. Chelsea 1952, 31.

3.    Guy R.K.: Unsohed Problems in Number Theory. Springer-VcrJag 1981

4.    Hardy G.H.. Wright E.M.: An Introduction to the Theory of Numbers. Wyd. 5, Oaford Univer-dty Press 1979.

5.    LcVequc W.J.: Fundamentah of Number Theory. Addison-Wesley 1977.

6.    Radcmaclicr H.: Lectures on Bementary Number Theory. Krieger 1977.

7.    Roscn K..H.: Bementary Number Theory and Us Applications. Wyd. 3, Addison-Wesley 1993.

8.    Schroeder M.R.: Number Theory in Science and Communication. Wyd. 2, Springcr-Vcrlag 1986.

9.    Shanks D.: Sobedand Unsohed Problems in Number Theory. Wyd. 3, Chelsea 1985.

10. Sierpiński W.: A Selection of Problems in the Theory of Numbers. Pergamon Press 1964.

11.    Spencer D.D.: Computers in Number Theory. Computer Science Press 1981

Ciała skończone i reszty kwadratowe

W tym rozdziale będziemy zakładali, że czytelnik zna podstawowe definicje i własności ciał. Przypomnimy teraz krótko, co będzie nam potrzebne.

1.    Ciałem jest zbiór F z działaniami dodawania i mnożenia, spełniającymi znane prawa - prawo przemienności i prawo łączności dla dodawania i mnożenia, prawo rozdzielności mnożenia względem dodawania, istnienie elementu neutralnego 0 dla dodawania, istnienie elementu neutralnego 1 dla mnożenia, istnienie elementów przeciwnych w dodawaniu i istnienie elementów odwrotnych do elementów różnych od zera w mnożeniu. Następujące przykłady ciał odgrywają ważną rolę w różnych działach matematyki: (1) ciało Q składające się ze wszystkich liczb wymiernych; (2) ciało R liczb rzeczywistych; (3) ciało C liczb zespolonych; (4) ciało Z/pZ liczb całkowitych modu-lo p, gdzie p jest liczbą pierwszą.

2.    Przestrzeń wektorowa (lub liniowa) nad dowolnym ciałem F może być zdefiniowana za pomocą tych samych własności, których używa się do definiowania przestrzeni wektorowych nad ciałem liczb rzeczywistych. Każda przestrzeń liniowa ma bazę; liczbę elementów bazy nazywamy wymiarem. Rozszerzenie ciała, tzn. większe ciało zawierające F, jest przestrzenią liniową nad F. Będziemy nazywać je rozszerzeniem skończonym, jeśli jest przestrzenią liniową skończonego wymiaru. Stopniem skończonego rozszerzenia nazywamy jego wymiar jako przestrzeni liniowej. Jednym ze sposobów otrzymywania rozszerzeń dał jest dołączanie elementów do ciała F: mówimy, że K = F(a), jeśli K jest ciałem składającym się ze wszystkich wyrażeń wymiernych utworzonych z u i elementów ciała F.

3.    Podobnie można zdefiniować pierścień wielomianów nad dowolnym dałem F. Jest on oznaczany przez F[Af]; składa się on ze skończonych sum potęg X ze współczynnikami z F. Wielomiany z F[2f] dodajemy i mnożymy w taki sam sposób jak wielomiany o współczynnikach rzeczywistych. Stopniem d wielomianu jest wykładnik najwyższej potęgi X, która występuje z nieze-rowym współczynnikiem; w wielomianie unormowanym ten współczynnik przy X^d jest równy 1. Mówimy, że g dzieli/, gdzie f geF[X], jeżeli istnieje wielomian beF[X] taki, że f — gh. Wielomian nierozkladalny feF[X] to