Aldeia Numaboa UM PORTAL DIFERENTE EM PORTUGUÊS DO BRASIL

Tutorial PARI/GP (II)

Detalhes

Categoria: Matemática Numaboa

Atualização: Domingo, 12 Abril 2009 16:14

Autor: vovó Vicki

Acessos: 9940

Esta é a segunda parte do tutorial PARI/GP, que dá continuidade ao PARI/GP I.

• Tipos da PARI intimamente ligados à Teoria dos Números

O primeiro é o tipo "módulo inteiro". Vejamos um exemplo. Digite n = 10^15 + 3. Queremos saber se este número é primo ou não. É claro que poderíamos usar outras facilidades oferecidas pela PARI, mas vamos fazer diferente. Primeiro, tentaremos uma divisão usando a tabela de números primos. Vamos dar uma enganadinha na PARI e usar a função factor que faz exatamente isto. Digite então factor(n, 200000) onde o último argumento pede para a factor dividir até este valor e depois parar. Se quiser o conjunto completo, cujo default é 500000, omita o segundo argumento.

Como em todas a funções de fatoração, o resultado é uma matriz de duas colunas: a primeira mostra os números primos e, a segunda, seus expoentes. Neste caso, obtivemos uma única linha mostrando que, se paramos nos primos até 200000, então n é um número primo, ou seja, n não é divisível por nenhum primo até 200000.

Podemos tentar dividir n por primos maiores ou enganar a função factor sem o segundo argumento mas, antes de fazer isto, é interessante ver como se pode obter a resposta com esforço próprio.

Pelo Pequeno Teorema de Fermat, se n for primo, precisamos ter n ^{n - 1} = 1 (mod n) para todos os a não divisíveis por n. Portanto, podemos tentar isto com, por exemplo, a = 2. Mas 2^{n - 1} é um número com aproximadamente 3*10¹⁴ dígitos, impossível de ser escrito e impraticável para ser usado em cálculos. Mas, se ao invés disso, digitarmos a = Mod(2, n), criamos o número 2 como um elemento do anel R = Z/nZ. Os elementos de R, chamados de intmods, sempre podem ser representados por números menores do que n, portanto, pequenos. O Teorema de Fermat pode ser reescrito como a^{n - 1} = Mod(1, n) no anel R, deste modo facilitando, e muito, os cálculos (os elementos de R podem ser transferidos para Z com lift ou centerlift). Agora, digite a^(n - 1). O resultado, definitivamente, não é igual a Mod(1, n), provando que n não é um número primo! Por outro lado, se tivéssemos obtido Mod(1, n), isto seria um indicativo de que n talvez fosse primo, mas nunca seria uma prova da sua primalidade.

Achar os fatores já é um outra história. Seria necessário usar uma técnica menos inocente do que a divisão por tentativa ou, então, ter uma paciência de Jó. Para terminar este exemplo, digite fa = factor(n) para ver os fatores. O fator menor é 14902357 e, o maior, 67103479.

Caso seu computador seja muito lento, encontrar esta solução pode ser um processo demorado. Neste caso, digite # para ligar o timer e, depois, for (i = 2, ceil(sqrt(n)), if (n%i==0, print(i); break)) para iniciar o loop de divisões. O seguinte loop de divisões é mais rápido e também funciona para este exemplo: for (i = 2, 14902357, n%i). Quando quiser desligar o timer, basta digitar # novamente.

É preciso saber que a maioria das funções produtoras de "primos", os fatores "primos" são apenas pseudoprimos fortes e não primos provados. Use isprime( fa[,1] ) para provar rigorosamente a primalidade dos fatores. Este comando citado aplica a função isprime() em todas as entradas da primeira coluna de fa, isto é, em todos os pseudoprimos, e retorna o vetor da coluna dos resultados. Como todos são iguais a 1, os pseudoprimos podem ser considerados primos verdadeiros. Todas as funções aritméticas podem ser aplicadas desta forma nas entradas de um vetor ou matriz. Na realidade, já foi conferido que os pseudoprimos fortes (pseudoprimos de Baillie-Pomerance-Selfridge-Wagstaff, sem divisores pequenos) obtidos através de factor são primos verdadeiros pelo menos até 10¹³ e nenhum exemplo provando o contrário é conhecido até o momento.

O segundo tipo da PARI específico da teoria dos números são os números p -ádicos. Neste tutorial não há espaço para definições e, se você não tiver uso para este tipo de monstro, então simplesmente pule este trecho ;) Um número p -ádico é fornecido como uma expressão cujo valor é racional ou inteiro, à qual é adicionado 0(p^n), ou simplesmente 0(p) se n = 1, onde p é primo e n é a precisão p-ádica. É preciso definir explicitamente a potência, por exemplo 3^2, porque valor 9 não funcionará (a não ser que você queira enganar a GP...). Além das operações aritméticas usuais, podemos aplicar algumas funções transcendentais. Por exemplo, digite n = 569 + 0(7^8) e, logo em seguida, s = sqrt(n) para obter uma das raízes quadradas de n (se quiser conferir, digite s^2 - n). Agora digite s = log(n) e e = exp(s). Se você está familiarizado com logaritmos p-ádicos, não será senhuma surpresa que e não seja igual a n. Entre (n / e)^6. Na verdade, e é igual a n vezes a (p - 1)ésima raiz da unidade teichmuller(n).

Mais uma coisa: se você quiser recuperar o inteiro 569 a partir do número p-ádico n, digite lift(n) ou truncate(n).

O terceiro tipo é o "número quadrático". Este tipo foi especialmente preparado para facilitar o trabalho com extensões quadráticas de um campo base (geralmente Q). Ele é uma generalização do tipo "complexo". Para começar, precisamos especificar em qual campo quadrático queremos trabalhar. Para isto, usamos a função quadgen aplicada ao discriminante d (como oposto do radicando) do campo quadrático. Isto retorna um número (sempre apresentado como w) igual a (d + a) / 2, onde a é igual a 0 ou 1, dependendo de d ser par ou ímpar. O comportamento da quadgen é um tanto especial: apesar do seu resultado ser sempre apresentado como w, a variável w não recebe este valor. Portanto, sempre é preciso escrever w = quadgen(d) usando o nome da variável w (ou w1, etc) se tivermos vários campos quadráticos. Se não procedermos desta forma, as coisas podem ficar um tanto confusas.

Depois desta breve introdução, digite w = quadgen(-163), depois charpoly(w), a qual busca as características polinomiais de w. O resultado mostra o que w representará. Você pode solicitar 1.*w para ver qual foi a raiz do quadrático usada, mas isto raramente é necessário. Agora podemos brincar com o campo Q(raiz quadrada de -163). Digite, por exemplo, w^10, norm(3 + 4*w), 1 / (4+w). Mais interessante ainda será digitar Mod(1, 23) * w e, depois, b = a^264. Esta é a generalização do teorema de Fermat para campos quadráticos. Se você não quiser ver o módulo 23 o tempo todo, digite lift(b).

Outro exemplo: entre com p = x^2 + w*x + 5*w + 7 e, depois, norm(p). Desta forma obtém-se a equação quártica de Q correspondente à extensão quadrática relativa de Q(w) definida por p.

Por outro lado, se você digitar wr = sqrt(w^2), não espere recuperar w. Ao invés disso, você obterá o valor numérico, com a função sqrt sendo considerada como uma função "transcendental", mesmo sendo algébrica. Digite algdep(wr, 2), pois isto procura pelas relações algébricas envolvendo as potências de w até o grau 2. Esta é uma das formas de recuperar w. De modo semelhante, você pode usar algdep(sqrt(3*w + 5), 4) (veja o manual para maiores detalhes desta função).

O quarto tipo é o "módulo-polinomial", isto é, o módulo polinomial de um outro polinômio. Este tipo é usado para trabalhar com extensões algébricas, por exemplo, elementos de campos numéricos (se o campo base for Q) ou elementos de campos finitos (se o campo base for Z/pZ para um primo p). De certo modo, é uma generalização do tipo número quadrático. A sintaxe usada é a mesma que a para intmods. Por exemplo, ao invés de digitar w = quadgen(-163), você pode entrar com w = Mod(x, quadpoly(-163)).

Deste modo, exatamente como no caso quadrático, você pode digitar w^10, norm(3 + 4*w), 1 / (4 + w), a = Mod(1, 23)*w, e b = a^264, obtendo os mesmos resultados (digite lift(...) se não quiser ver o polinômio x^2 - x + 41 sendo repetido o tempo todo). É claro que se pode trabalhar com qualquer grau, não apenas o quadrático. Para os não quadráticos, as operações elementares correspondentes serão mais lentas. Inicie o timer e depois compare:

    w = quadgen(-163); W = Mod(x, quadpoly(-163));
    a = 2 + w; A = 2 + W;
    b = 3 + w; B = 3 + W;
    for (i=1,10^5, a+b)
    for (i=1,10^5, A+B)
    for (i=1,10^5, a*b)
    for (i=1,10^5, A*B)
    for (i=1,10^5, a/b)
    for (i=1,10^5, A/B)

(Não redigite tudo, use as teclas das setas!)

No entanto, existe um pequena diferença de comportamento. Mantendo o nosso polmod w, digite 1.*w. Como você pode verificar, o resultado não é o mesmo. Digite sqrt(w). Aqui obtemos um vetor com 2 componentes, os dois sendo o ramo principal da raiz quadrada de todas as ocorrências de w em C (e não as duas raízes quadradas). Mais genericamente, se w era de grau n, obteríamos um vetor de n componentes e, de forma semelhante, para todas as funções transcendentais.

A PARI oferece funções aritméticas usuais além de algumas outras. Digite a = Mod(x, x^3 - x - 1) para definir uma extensão cúbica. Podemos, por exemplo, chamar b = a^5. Agora imagine que queiramos exprimir a como um polinômio de b. Isto é possível porque b também é um gerador do mesmo campo. Não tem problema, basta digitar modreverse(b). Isto dá um novo polinômio definidor para o mesmo campo (isto é, o polinômio característico de b) e expressa a em termos deste novo polmod, isto é, em termos de a.