Fatoração de polinômios univariados

Universidade Federal do Rio Grande do Sul XXIII Salão de Iniciação Científica

Fatoração de polinômios univariados

Jéssica Lopes dos Santos Instituto de Matemática - UFRGS

Aplicações
• Raízes de polinômios • Zeros de funções aproximadas por polinômios

Introdução
Nesta apresentação, será exposto um algoritmo de fatoração de polinômios univariados sobre um corpo finito Fq onde q é o número de elementos em F e vamos desenvolver um dos passos desse algoritmo que é a fatoração em graus distintos.

Definição de Corpo: Um conjunto K é um corpo se as seguintes propriedades são satisfeitas para quaisquer a, b, c ϵ K:

(a) (a + b) + c = a + (b + c) (b) ∃ 0 ∈ K tal que a + 0 = 0 + a = a (c) ∀ x ∈ K existe um único y ∈ K, denotado x + y= y+x =0 (d) a + b = b + a (e) (a b) c = a (b c) (f) a (b + c) = a b + a c, (a + b) c = a c + b c (g) ∃ 1 ∈ K, 1 ≠ 0, tal que x ⋅ 1 = 1 ⋅ x = x, ∀ x ∈ K (h) ∀ x, y ∈ K, x ⋅ y = y ⋅ x (i) x, y ∈ K, x ⋅ y = 0 ⇔ x = 0 ou y = 0 (j) ∀ x ∈ K, x ≠ 0, ∃ y ∈ K tal que x ⋅ y = y ⋅ x = 1 por y = - x, tal que

Consideremos agora o corpo F e seja F[x] o conjunto de todos os polinômios f com coeficientes em F e indeterminada x onde f(x) = a0 + a1x + ... + anxn, n = 1,2,... • f é um polinômio mônico irredutível sobre F se e somente se, para f não constante, a e b ϵ F[x] tem-se f = ab com a ou b igual a uma constante. • f é dito livre de quadrados se, para algum g ϵ F[x] tivermos g2|f(x) então g tem grau zero.

Tomemos Fq corpo finito com q elementos. Utilizaremos os seguintes teoremas que não serão demonstrados nesta apresentação:

Pequeno teorema de Fermat Para algum a ϵ Fq, a não zero, tem-se aq-1 = 1 e para todo a ϵ Fq, tem-se aq = a e

xq − x =
Teorema

∏ ( x − a) a∈ F q

em Fq[x]

Para algum d ≥ 1, x ϵ Fq[x] é o produto de todos os polinômios mônicos irredutíveis em Fq[x] onde o grau divide d. A demonstração deste teorema tem como base o teorema anterior.

qd

A decomposição em graus distintos de um polinômio não