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: 9870

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.

• Funções aritméticas elementares

Como a PARI foi projetada para teóricos dos números, não é de se surpreender que ofereça um grande número de funções aritméticas (veja a lista delas digitando ?4). Já vimos várias delas, como a factor. Saiba que a função factor não lida apenas com números inteiros, mas também com polinômios (univariados). Digite, por exemplo, factor(x^200 - 1). Você também pode pedir para fatorar um módulo polinomial a primo p (factormod) e até mesmo num campo finito que não seja um campo primo (factorff).

Evidentemente existem funções para computar o máximo divisor comum (gdc), o máximo divisor comum estendido (bezout), resolver o teorema chinês dos restos (chinese) e assim por diante.

Além das facilidades de fatoração, existem algumas funções relacionadas a testes de primalidade, como isprime, ispseudoprime, precprime e nextprime. Como foi mencionado anteriormente, apenas pseudoprimos fortes são produzidos pelas duas primeiras funções (elas passam o teste ispseudoprime). Os testes de primalidade mais sofisticados de isprime, sendo muito mais lentos, não são aplicados como default.

As funções aritméticas multiplicativas também estão presentes: a função µ de Möbius (moebius), a função φ de Euler (eulerphi), as funções ω e Ω (omega e bigomega), as funções σ_k (sigma) que calculam a k-ésima potência dos divisores positivos de um dado inteiro, etc.

Você pode calcular frações contínuas. Por exemplo, entre com \p 1000, depois com contfrac(exp(1)) para obter a fração contínua da base dos logaritmos naturais que, como se pode ver, obedece a um padrão muito simples.

Em muitos casos, queremos realizar determinada tarefa somente se uma determinada condição aritmética for satisfeita. A GP oferece as seguintes funções: isprime, como mencionado acima, issquare, isfundamental para testar se um inteiro é um discriminante fundamental (isto é, 1 ou o discriminante de um campo quadrático), e os loops forpeimw, fordiv e sumdiv. Imagine que se queira calcular o produto de todos os divisores positivos de um inteiro positivo n. A maneira mais fácil é escrever p = 1; fordiv(n,d, p *= d); p. A notação p *= d é apenas uma forma abreviada de p = p * d.

Se quisermos saber a lista dos números primos p menores do que 1000, de modo que 2 seja uma raiz primitiva módulo p, poderíamos escrever forprime(p=3,1000, if (znprimroot(p) == 2, print(p))). Observe que isto pressupõe que znprimroot retorne a menor raiz primitiva e este é efetivamente o caso. Se soubéssemos disso, poderíamos ter escrito forprime(p=3,1000, if (znorder(Mod(2,p)) == p-1, print(p))) (que é mais rápido porque apenas calculamos a ordem de 2 em Z/pB ao invés de procurar por um gerador testando elementos sucessivos cujas ordens também precisam ser calculadas).

Acho que vou parar por aqui, por que já tem material suficiente para fundir a cabeça da maioria das pessoas

vovó Vicki