O algoritmo de Berlekamp

A teoria de corpos finitos é bastante importante, tanto em questões teóricas, ligadas principalmente à Teoria dos Números, bem como em aplicações práticas envolvendo criptografia e códigos corretores de erros. Frequentemente, é necessário saber se um dado polinômio sobre um corpo finito é irredutível (por exemplo, para construir explicitamente outros corpos finitos) ou até mesmo encontrar uma fatoração completa para tal polinômio. Neste último caso, uma aplicação corrente é para resolver o problema do logaritmo discreto, essencial em criptografia: certos algoritmos envolvem fatorações de elementos de um corpo finito, cujos elementos podem ser representados como classes de equivalência de polinômios sobre o corpo primo, daí a utilidade de um algoritmo para fatorar polinômios.

Em geral, em se tratando de um corpo qualquer, testar irredutibilidade é uma tarefa complicada, e fatorar um polinômio em irredutíveis é mais complicado ainda. No entanto, em se tratando de corpos finitos, existe um algoritmo bastante simples e inteligente! Neste post vou explicar a ideia deste algoritmo, como sempre, do ponto de vista matemático, sem me envolver com questões de implementação (embora não seja difícil) ou de complexidade.

Vale ressaltar que, atualmente - ou seja, se você está lendo este post depois de 1981-, existe um algoritmo mais eficiente que o algoritmo de Berlekamp. Além disso, utilizando truques engenhosos, algoritmos para fatorar polinômios em corpos finitos também são utilizados para fatorar polinômios em , por exemplo.

Os requisitos para entender o que se sucede são:

• Linguagem básica de teoria de anéis (morfismos, ideais, ideais principais, fatoração única, etc).
• Uma certa familiaridade com anéis de polinômios (coisas básicas, como noção de coprimo).
• Um pouco de teoria de corpos (extensões de corpos, etc) e noções de corpos finitos (na verdade, tudo o que você precisa saber é que, para primo, é um corpo, que denotamos ).

1. Teolema Chinês dos Lestos

O algoritmo de Berlekamp se baseia em duas ferramentas algébricas: o teorema chinês dos restos e o morfismo de Frobenius. Por "teorema chinês dos restos", entendemos a sua versão mais geral, envolvendo ideais. Aqui, precisaremos apenas de um caso particular, no anel de polinômios de um corpo.

Teorema. Seja um corpo e polinômios dois a dois coprimos entre si. Se , então o mapa natural

é um isomorfismo de anéis.

Se quiser, pule esta demonstração, está um pouco curta e grossa porque não é o objetivo do post. ;-)

Demonstração. O mapa é injetivo pois são coprimos entre si e estamos num domínio de fatoração única. Para mostrar que o mapa é sobrejetivo, basta mostrar que, para cada , existe tal que , e , . Note que, se , então é invertível módulo (pois são coprimos); logo existe tal que . Basta tomar .

2. O morfismo de Frobenius

Lembremos rapidamente que temos a noção de característica de um anel. Dado um anel qualquer, existe sempre um único morfismo de anéis que leva na identidade multiplicativa de . Como os ideais de são todos principais, existe tal que . Dizemos então que tem característica . Em outras palavras, é o menor natural tal que em .

Observação: Se é um domínio, por exemplo um corpo, o núcleo de é um ideal primo e, portanto é igual a ou com primo.

Observação: Se é um anel de característica , então e o morfismo induz um morfismo injetivo . Neste caso, identificando com a sua imagem, podemos pensar . Por exemplo, se , então a cópia de dentro de é dada pela "diagonal": .

Mesmo quando não é um domínio, a noção de característica só se torna realmente relevante quando ela é ou um número primo e estamos interessados aqui no segundo caso.

Proposição. Se é um domínio de característica primo, o mapa , dado por , é um morfismo, denominado morfismo de Frobenius.

Demonstração. É claro que e que, dados , . Resta mostrar que . Para isto é só utilizarmos o fato (trivialmente verificável) que se , donde

Observação: O fato de que, num anel de característica , termos é usualmente conhecido em inglês como "freshman's dream". Em português, a denominação corrente (???) é o "sonho de todo estudante".

Apesar de parecer inocente, a primeira vista, o morfismo de Frobenius não deve ser subestimado! É graças a ele, por exemplo, que conseguimos compreender com bastante detalhes a Teoria de Galois dos corpos finitos. Na verdade, é praticamente uma heresia falar de corpos finitos sem falar do morfismo de Frobenius!

Exemplo. Considere . Então o morfismo de Frobenius é a identidade. Isto é apenas uma outra formulação do Pequeno Teorema de Fermat (ou o Teorema de Lagrange): todo elemento não nulo é tal que , multiplicando por obtemos , que também é verdade para . Logo, para todo , .

Exemplo. Se é um corpo de característica e é o morfismo de Frobenius, então . De fato, pelo exemplo anterior, temos já a inclusão . Por outro lado se, e somente se, é raiz do polinômio que (aqui usamos que é um corpo) possui no máximo raízes. Logo devemos ter a igualdade.

3. Testando irredutibilidade

Considere o corpo finito . Dado um polinômio queremos decidir se é irredutível ou não.

Atenção! Vamos nos restringir, primeiramente, ao caso onde não tem fator quadrado, ou seja, não existe tal que . Isto é somente uma restrição técnica, que mostraremos no final que não é um grande problema.

Com a hipótese acima, podemos supor que a fatoração de em irredutíveis é da forma , irredutível, . Observamos desde já que é irredutível se, e somente se . A ideia do algoritmo consiste "linearizar o problema" para determinar .

Considere a álgebra . Pelo teorema chinês dos restos, sabemos que temos um isomorfismo de anéis

onde cada é um corpo (pois é irredutível), que é uma extensão finita de . Agora observamos que o número é exatamente o número de corpos que aparece na decomposição acima. Como determiná-lo?

Aqui entra a ideia simples e genial. Note que é um anel de característica . Considere o morfismo de Frobenius . Quem são os pontos fixos de ? Temos:

onde a última igualdade é devida ao último exemplo da seção anterior. Em outras palavras, . Ora, é um mapa linear e não é nada mais que . Assim, para calcular , basta computar a matriz do mapa linear e encontrar a dimensão do seu núcleo, por exemplo, utilizando eliminação de Gauss!

Exemplo. Vamos fazer um exemplo com um caso pequeno para ver como funciona. Suponha e considere . É fácil checar que este polinômio é irredutível (basta verificar que ele não possui raiz em ), mas mostremos o mesmo fato utilizando Berlekamp. Primeiro consideramos a álgebra . Se denota a classe de em , temos que uma base para como espaço vetorial é: . Em geral, para implementar o algoritmo de fato, usamos uma base como esta.
Vamos calcular a matriz de nesta base: observe que temos a relação . Em particular,

e

Assim,

e a matriz fica

e é claro que as duas últimas colunas são linearmente independentes. Logo a dimensão do núcleo desta matriz é , ou seja, é irredutível.

Bem, deu para perceber que uma ideia melhor é usar um computador. ;-)

4. Fatorando completamente

O algoritmo de Berlekamp não para por aí. Vejamos o que acontece caso é maior que . Neste caso, existe um "vetor não-constante" em , ou seja, existe , com tal que sua imagem em pertence a . Ou seja,

Agora note que o polinômio se fatora completamente neste anel (de novo estamos utilizando o fato que o morfismo de Frobenius é a identidade), isto é, . Substituindo e usando a equação acima, obtemos

Agora afirmamos que existe tal que é um polinômio não-constante, em particular, um fator não-trivial de ! De fato, como divide , temos

Se , , então e são primos entre si, pois diferem de um elemento de .

Lema. Se é um domínio de fatoração única, , com e primos entre si, então .

Demonstração. Exercício. ;-)

Logo, como os fatores do produto são dois a dois primos entre si, temos portanto

Observe que, para todo , . Além disso, existe pelo menos um tal que não é constante (caso contrário seria constante). Pronto, é um fator não trivial de !

Resumindo, na prática, encontramos o polinômio que corresponde a um elemento não-constante de e vamos alterando o seu termo constante até achar um a tal que divide . O argumento acima garante que sempre vamos encontrar um tal .

Depois disso, fazemos uma recorrência, aplicando o algoritmo aos polinômios e , até encontrar os fatores irredutíveis (em geral, não será irredutível).

5. Ajuste final

Estamos sempre trabalhando sobre a hipótese de que não possui fatores quadrados. Qual é o problema? Neste caso, a fatoração em irredutíveis de é da forma geral , com inteiro, . Eventualmente, algum pode ser maior que um. Agora o número não diz nada sobre a redutibilidade de . Isto é, poderia ser da forma , com irredutível, . Se tentarmos aplicar o mesmo método, temos e (demonstre!) , ou seja, , muito embora seja redutível.

Em resumo, não há esperança de fazer um argumento parecido que também funcione com polinômios com fator quadrado. Mas nem tudo está perdido. Na realidade, este caso é bastante fácil de ser tratado.

Suponha que existe , , tal que . Isto é, podemos escrever , com . Então . Portanto, . Assim, , facilmente calculado com o algoritmo de Euclides, é um candidato a fator não-trivial de $P$, mas pode acontecer de . Separamos em dois casos:

1. Se (ou, equivalentemente, ), então , pois e . Neste caso, é fácil verificar, todos os monômios que aparecem em têm grau múltiplo de , isto é, podemos escrever . Como, para cada , , obtemos (estamos usando aqui que é um morfismo). Em particular, o polinômio é um fator não-trivial de .
2. Se , o polinômio é um fator não-trivial de

Encontrado um fator não-trivial de , fazemos uma recorrência até atingir polinômios separáveis e, depois, usamos o algoritmo de Berlekamp acima. Desta maneira, fatoramos completamente o nosso polinômio. Yay!

6. Um comentário e links pra galera

Aqui tomamos sempre como corpo base o corpo , mas poderíamos ter considerado qualquer corpo finito. Em geral, um corpo finito é sempre da forma , inteiro, e o morfismo de Frobenius a ser considerado é a composta de vezes, isto é: . Todo o resto funciona igual.

Se você quiser dar mais uma lida sobre o assunto, aqui vão umas sugestões:

• Página da Wikipédia sobre o Algoritmo. Contém um link no final com o paper original do Berlekamp que parece ser fácil de ler (apesar de eu só ter passado o olho rapidamente). Essencialmente, ele explica a mesma coisa deste post, com menos detalhes. A vantagem de lê-lo é que você pode tirar uma onda com as garotas, dizendo que já lê artigos recentes de álgebra.
• Página da Wikipédia contendo informações gerais sobre fatoração de polinômios.
• Página profissional do próprio Berlekamp. Ele ainda tá na ativa!