-
inele de polinoame
- inelul F[x] de polinoame in x peste campul F
- fie (F,+,.) un camp; un polinom de variabila x peste F este o expresie de forma f(x) = a0+a1 . x + a2 . x2 + ... + an . xn unde coeficientii ai sunt elemente ale lui F si n este un intreg pozitiv
cel mai mare i ptr. care ai ≠ 0 se numeste gradul lui f(x)
∀ F, inelul F[x] este un domeniu de integritate - polinom ireductibil
- fie f(x) ∈ F[x] un polinom cu gradul cel putin 1. Se spune ca f(x) este ireductibil peste F daca nu poate fi scris ca produsul a doua polinoame din F[x], fiecare de grad pozitiv
- impartire
- fie g(x), h(x) ∈ F[x] cu h(x) ≠ 0 at g(x) = c(x)h(x) + r(x) cu grad r(x) < grad h(x), c(x) si r(x) sunt unice
c(x) se noteaza g(x) div h(x0 si r(x) se noteaza g(x) mod h(x) - divizor
- fie g(x), h(x) ∈F[x]; h(x) divide pe g(x) , h(x)|g(x) daca g(x) mod h(x) = 0
- congruenta
- fie g(x), h(x) ∈F[x]; se spune ca g(x) este congruent cu h(x) modulo f(x) daca f(x)| g(x)-h(x) si se noteaza g(x) ≡ h(x) (mod f(x))
congruenta are proprietatile unei relatii de echivalenta: reflexivitate, simetrie si tranzitivitate - clase de echivalenta
- multimea claselor de echivalenta modulo f(x) ale polinoamelor peste F[x] se noteaza F[x]/(f(x))
F[x]/(f(x)) cu adunarea si inmultirea modulo f(x) formeaza un inel comutativ
daca f(x) este ireductibil peste F[x] at. F[x]/(f(x)) este camp
-
campuri finite
- camp finit
- un camp F care are un numar finit de elemente
ordinul lui F este numarul sau de elemente - existenta si unicitate
- daca F este un camp finit at F contine pm elemente unde p este prim si m este un intreg pozitiv
- ptr fiecare pm exista un camp finit unic (clasa de izomorfism) de ordinul pm; campul se noteaza Fpm sau GF(pm)
- T
- daca F este un camp de ordin q=pm cu p prim at. caracteristica lui Fq este p
- Fq contine o copie a lui Zp ca subcamp
- ∀ subcamp al lui Fq are ordinul pn unde n este un divizor pozitiv al lui m
- grupul multiplicativ F*q
- elementele nenule ale lui Fq formeaza grup cu inmultirea
- F*q grup ciclic
- de ordinul q-1
- element generator
- un generator al lui F*q se numeste generator pentru Fq
- T
- ( a + b ) pt = a pt + b pt cu a, b ∈ Fq si p caracteristica campului
- Euclid in Zp[x]
-
- cmmdc
fie g(x), h(x) ∈ Zp[x], ambele nenule; cmmdc(g(x), h(x)) este monomul cu cel mai mare grad care divide pe g(x) si pe h(x)
- Zp[x] este domeniu unic de descompunere in factori
∀ f(x) ∈ Zp[x] admite o descompunere in factori de forma f(x) = a f1(x)e1f2(x)e2...fk(x)ek unde fi(x) sunt monoame ireductibile in Zp[x] si ei sunt intregi pozitivi iar a ∈ Zp
descompunerea este unica
- algoritm Euclid
- intrare: g(x), h(x) ∈ Zp[x]
- iesire: cmmdc(g(x), h(x))
- while h(x) ≠ 0 do
r(x)=g(x) mod h(x) , g(x)=h(x) , h(x) = r(x)
- return g(x)
algoritm cu O(m2) operatii in Zp sau O(m2(lg p)2) operatii binare
- algoritm Euclid extins
- intrare: g(x), h(x) ∈ Zp[x]
- iesire: d(x) = cmmdc(g(x), h(x)) si doua polinoame s(x) , t(x) ∈ Zp[x] care satisfac: s(x)g(x) + t(x)h(x) = d(x)
- if h(x) = 0 then d(x)=g(x), s(x) = 1, t(x)=0 , return (d(x),s(x),t(x0)
- else s2(x)=1, s1(x)=0, t2(x)=0, t1(x)=1
- while h(x) ≠ 0 do
q(x)=g(x) div h(x), r(x)=g(x)-h(x)q(x)
s(x)=s2(x)-q(x)s1(x), t(x)=t2(x)-q(x)t1(x)
g(x)=h(x), h(x)=r(x)
s2(x)=s1(x), s1(x)=s(x), t2(x)=t1(x), t1(x)=t(x)
- d(x)=g(x), s(x)=s2(x), t(x)=t2(x)
- return (d(x),s(x),t(x0)
algoritm cu O(m2) operatii in Zp sau O(m2(lg p)2) operatii binare
- aritmetica polinoamelor
- polinoame ireductibile
- functia Möbius, μ
| 1 | daca m=1 |
| 0 | daca m este divizibil cu patratul unui numar prim |
| (-1)k | daca m este produsul a k numre prime distincte |
- numarul de polinoame ireductibile de grad m in Zp[x] este Np(m) = 1/m Σd|m μ(d)pm/d
- algoritm testare ireductibilitate polinom
- intrare: un nuamr prim p si un monom f(x) de grad m in Zp[x]
- iesire: raspuns la intrebarea "este f(x) ireductibil ?"
- u(x)=x
- for i from 1 to [m/2]
u(x) = u(x)p mod f(x) (prin algoritmul de exponentiere)
d(x) = cmmdc(f(x), u(x)-x)
if d(x) ≠ 1 return "reductibil"
- return "ireductibil"
- algoritm calcul inversului
- intrare: un polinom nenul g(x) ∈ Fpm (elementele campului Fpm sunt reprezentate ca Zp[x]/(f(x)) unde f(x) este un polinom ireductibil de grad m peste Zp
- iesire: g(x)-1 ∈ Fpm
- se aplica Euclid extins pentru a gasi s(x) si t(x0 ai s(x)g(x)+t(x)f(x) = 1
- se returneaza s(x)
- algoritm exponentiere
- intrare: g(x) ∈ Fpm, un intreg 0 ≦ k < pm-1 ce are reprentarea binara k = Σ i=0t ki2i
- iesire: g(x)k mod f(x)
- s(x)=1; if k=0 then return s(x0
- G(x)=g(x)
- if k0=1 then s(x)=g(x)
- for i from 1 to t do
G(x)=G(x)2 mod f(x)
if ki=1 then s(x)=G(x)s(x) mod f(x)
- return s(x)
- complexitatea operatiilor
| operatia | complexitatea (numarul de operatii Zp) |
| adunare | O(m) |
| scadere | O(m) |
| inmultire | O(m2) |
| inversare | O(m2) |
| exponentiere | O(m3lg(p)) |
- polinom primitiva
- este un polinom ireductibil f(x) ∈ Zp[x] de grad m care este genrator al grupului multiplicativ F*q
- f(x) este polinom primitva ⇔ f(x) divide xk-1 pentru k=pm-1
- ptr m ≧ 1 exista φ(pm-1)/m monoame primitive de grad m peste Zp
- algoritm testarea primitivitatii unui polinom ireductibil
- intrare: un numar prim p, un intreg pozitiv m, factorii primi distincti r1, r2, ,,,, rt si un polinom ireductibil de grad m, f(x)
- iesire: un raspuns la intrebarea "este f(x) primitiva?"
- for i from 1 to t do
l(x) = x(pm-1)/ri
if l(x) =1 return "nu este primitiva"
- return "este primitiva"
# posted by Sorin Badescu @ 1:00 PM
