DQSoft: Números Primos

Desde o começo da matemática os números primos fascinam as pessoas. Este interesse aumentou com o advento dos computadores, tanto no que diz respeito à descoberta de números primos como ao seu uso em algorítimos, particularmente na criptografia.

Neste post vou falar um pouco sobre os números primos, a geração da lista de primos até um certo número e como testar se um número é primo.

Este é um assunto que rapidamente fica complexo, ultrapassando o meu conhecimento atual. Recomendo as referências no final para quem quiser saber mais sobre o assunto.

Definição

Um número primo é um número inteiro positivo que tem exatamente dois divisores distintos: 1 e ele mesmo.

Alguns comentários sobre esta definição:

O conceito de número primo não se aplica ao zero e aos números negativos.
O número 1 não é primo. Até o século 19 ele era considerado primo por muitos matemáticos, mas as vantagens em considerá-lo não primo levaram à inclusão do "distintos" na definição (vide aqui).

O Teorema Fundamental da Aritmética determina que todo número inteiro maior que 1 pode ser escrito como um produto único (não considerando a ordem dos fatores) de números primos. O processo de determinar estes fatores é chamado de fatoração.

Listando Primos

Não sei se isto ainda é tradicional, mas uma atividade típica de primário era fazer o Crivo de Erastóteles (veja aqui uma animação). Basicamente você faz uma lista com os números de 2 a N, 2 é o primeiro primo. Aí você vai cortando os números de 2 em 2 (ou seja, excluindo os múltiplos de 2). Chegando ao fim da lista, volte a examinar o início e veja qual é o próximo não cortado (no caso o 3), é próximo primo. Repita o processo, agora cortando de 3 em 3, e assim por diante.

Uma versão mais moderna, e um pouco mais rápida, é o Crivo de Atkin.

Se você quiser receber por e-mail uma lista de números primos, você pode solicitar aqui. Você deve especificar uma faixa de até 1 milhão de números e a página trabalha com números até 10 bilhões.

Testando Se Um Número é Primo

A primeira vez que eu tentei descobrir se um número era primo eu parti do método óbvio (que as minhas fontes se referem como "ingênuo" ou "da Idade das Trevas"): testar a divisão por todos os números menores que ele. Imediatamente percebi, que poderia pular os números pares e interromper a busca na raiz quadrada do número. O código em C abaixo mostra este método:


int Primo (int n)
{
    int i, limite;

    if (n == 2)
        return TRUE;
    if ((n < 2) || ((n % 2) == 0))
        return FALSE;
    limite = (int) ceil(sqrt (n));
    for (i = 3; i <= limite; i += 2)
        if ((n % i) == 0)
            return FALSE;
    return TRUE;
}

Um aperfeiçoamento (ainda ingênuo, mas já fora do meu alcance) é testar a divisibilidade por 2, 3 e números na forma 6k ± 1. É o que faz o código abaixo:


int Primo (int n)
{
    int k, m, limite;

    if ((n == 2) || (n == 3))
        return TRUE;
    if ((n < 2) || ((n % 2) == 0) || ((n % 3) == 0))
        return FALSE;
    limite = (int) ceil(sqrt (n));
    for (k = 1; ; k++)
    {
        m = 6*k - 1;
        if (m > limite)
            break;
        if ((n % m) == 0)
            return FALSE;
        m = 6*k + 1;
        if (m > limite)
            break;
        if ((n % m) == 0)
            return FALSE;
    }
    return TRUE;
}

Uma outra possibilidade é colocar no programa uma tabela de números primos e testar a divisão por eles. Esta tabela pode ser compactada guardando no lugar dos números primos a diferença entre eles ou a metade desta diferença. Para os primos de 3 a 436.273.009 a diferença em relação ao anterior nunca ultrapassa 256, podendo ser armazenada em um único byte. Guardando metade da diferença (que sempre é par pois os primos maiores que dois são ímpares), dá para guarda em bytes os primos até 304.599.508.537.

Os testes mais modernos mais usados são probabilísticos. Eles são capazes de indicar com precisão que um número não é primo, mas podem indicar como primo um número composto. Estes testes, por serem relativamente rápidos, são usados para uma primeira verificação. Um exemplo destes métodos é o Miller-Rabin.

Curiosamente, alguns métodos probabilísticos podem ser usados para determinar com certeza se um número é primo, desde que se imponha um teto para o número. Neste exemplo, é utilizado o conceito de SPRP (strong probable-prime), que é um teste probabilístico "parametrizado" por uma base. Considerando os inteiros sem sinal de 32 bits, existe somente uma exceção (um falso positivo) que passa pelos testes com as bases 2, 3, 5 e 7. Isto leva ao exemplo abaixo, adaptado diretamente do código que você encontra aqui:


/*
    Primo3 - Teste de número primo baseado em SRP (strong probable-prime)
             Adaptado de código escrito por Olivier Langlois <olivier@olivierlanglois.net>

    Referências:
    http://primes.utm.edu/prove/prove2_3.html
    http://www.olivierlanglois.net/archive/prime_cpp.htm

*/

#include <stdio.h>

#define FALSE 0
#define TRUE  1


// Return (x*y)%z
unsigned mulmod( unsigned x, unsigned y, unsigned z )
{
  unsigned lxy, hxy = 0;
  unsigned lx,ly,hx,hy;

  x = x%z;
  y = y%z;

  hx = x>>16;
  hy = y>>16;

  if( (hx == 0) && (hy == 0) )
  {
      lxy = x*y;
  }
  else
  {
    unsigned c;

    lx = x & 0x0000ffff;
    ly = y & 0x0000ffff;

    c = lx*ly;
    lxy = c & 0x0000ffff;
    c = (c>>16) + ly*hx;
    hxy = c>>16;
    c = (c & 0x0000ffff) + hy*lx;
    lxy |= ((c & 0x0000ffff)<<16);
    hxy += (c>>16) + hy*hx;
  }

  while(hxy--)
  {
      unsigned tmp = 0xffffffff;
      lxy %= z;
      tmp -= (z - 1);
      lxy += tmp;
  }

  return lxy%z;
}

/******************************************************************************
 *
 * Name      : modexpo
 *
 * Purpose   : Compute a^b MOD m for b >= 0
 *
 * Note      : Can produce an overflow if the platform id not x86.
 *
 * Reference : D. M. Bressoud, Factorization and Primality Testing,
 *             Undergraduate Texts in Mathematics, Springer-Verlag,
 *             New York, 1989 (QA161.F3B73, ISBN 3-540-97040-1).
 *             Algorithm 3.3 p.34
 *
 ****************************************************************************/
unsigned modexpo( unsigned a, unsigned b, unsigned m )
{
    unsigned n = 1;

    /*
     * We find the binary representation of b while at the same time
     * computing successive squares of a. The variable n records the product
     * of the powers of a.
     */
    while( b > 0 )
    {
        if( b & 1 )
            n = mulmod( n, a, m );

        b >>= 1;
        a = mulmod( a, a, m );
    }

    return n;
}

/******************************************************************************
 *
 * Name      : b_SPRP
 *
 * Purpose   : Strong Probable Prime test to the base b
 *
 * Note      : Can produce an overflow if the platform id not x86.
 *
 * Reference : D. M. Bressoud, Factorization and Primality Testing,
 *             Undergraduate Texts in Mathematics, Springer-Verlag,
 *             New York, 1989 (QA161.F3B73, ISBN 3-540-97040-1).
 *             Algorithm 6.1 p.77
 *
 ****************************************************************************/
int b_SPRP( unsigned n, unsigned b )
{
    unsigned t = n - 1;
    unsigned nMinus1 = t;
    unsigned a = 0;
    unsigned test;

    /*
     * Find t and a satisfying: n-1=2^a * t, t odd
     */
    while( !(t & 1) )
    {
        t >>= 1;
        a++;
    }

    /*
     * We check the congruence class of b^((2^i)t) % n for each i
     * from 0 to a - 1. If any one is correct, then n passes.
     * Otherwise, n fails.
     */
    test = modexpo(b, t, n);
    if( test == 1 || test == nMinus1 )
        return  TRUE;

    while( --a )
    {
        test = mulmod(test, test, n);
        if( test == nMinus1 ) 
            return TRUE;
    }

    return FALSE;
}

/*
 If n < 25,000,000,000 is a 2, 3, 5 and 7-SPRP, then either 
 n  = 3,215,031,751 or n is prime
*/
int Primo (unsigned n)
{
    if (n == 3215031751)
        return FALSE;
    if (n <= 10)
    {
        return (n == 2) || (n == 3) || (n == 5) || (n == 7);
    }
    if ((n % 2) == 0)
        return FALSE;
    return b_SPRP (n,2) && b_SPRP (n,3) && b_SPRP (n,5) && b_SPRP (n,7);
}

// Programa de teste
int main (void)
{
    unsigned n, cont = 0;

    for (n = 1; n < 100000; n++)
        if (Primo(n))
        {
            cont++;
            printf ("%d\n", n);
        }
    printf ("%d Primos\n", cont);
}