1.2.6 Exemplo: Testando Primalidade

Esta seção descreve dois métodos para verificar a primalidade de um inteiro $n$, um com ordem de crescimento $\Theta(\sqrt{n})$, e um algoritmo "probabilístico" com ordem de crescimento $\Theta(\log n)$. Os exercícios ao final desta seção sugerem projetos de programação baseados nesses algoritmos.

Buscando divisores

Desde os tempos antigos, matemáticos têm sido fascinados por problemas concernentes a números primos, e muitas pessoas trabalharam no problema de determinar maneiras de testar se números são primos. Uma maneira de testar se um número é primo é encontrar os divisores do número. O programa a seguir encontra o menor divisor integral (maior que 1) de um dado número $n$. Ele faz isso de uma maneira direta, testando $n$ para divisibilidade por inteiros sucessivos começando com 2.

Exemplo de Código

function smallest_divisor(n) {
  return find_divisor(n, 2);
}
function find_divisor(n, test_divisor) {
  return square(test_divisor) > n
         ? n
         : divides(test_divisor, n)
         ? test_divisor
         : find_divisor(n, test_divisor + 1);
}
function divides(a, b) {
  return b % a === 0;
}

function smallest_divisor(n) { return find_divisor(n, 2); } function find_divisor(n, test_divisor) { return square(test_divisor) > n ? n : divides(test_divisor, n) ? test_divisor : find_divisor(n, test_divisor + 1); } function divides(a, b) { return b % a === 0; }

⛓ sessão — este bloco compartilha o ambiente da página: as declarações dos blocos anteriores são avaliadas antes deleCódigo editável · Ctrl+Enter executa · Esc solta o foco

Podemos testar se um número é primo da seguinte forma: $n$ é primo se e somente se $n$ é seu próprio menor divisor.

Exemplo de Código

function is_prime(n) {
  return n === smallest_divisor(n);
}

function is_prime(n) { return n === smallest_divisor(n); }

⛓ sessão — este bloco compartilha o ambiente da página: as declarações dos blocos anteriores são avaliadas antes deleCódigo editável · Ctrl+Enter executa · Esc solta o foco

O teste de fim para find_divisor é baseado no fato de que se $n$ não é primo, ele deve ter um divisor menor ou igual a $\sqrt{n}$.¹ Isso significa que o algoritmo só precisa testar divisores entre 1 e $\sqrt{n}$. Consequentemente, o número de passos necessários para identificar $n$ como primo terá ordem de crescimento $\Theta(\sqrt{n})$.

O teste de Fermat

O teste de primalidade $\Theta(\log n)$ é baseado em um resultado da teoria dos números conhecido como Pequeno Teorema de Fermat.²

Pequeno Teorema de Fermat: Se $n$ é um número primo e $a$ é qualquer inteiro positivo menor que $n$, então $a$ elevado à $n$-ésima potência é congruente a $a$ módulo $n$.

(Dois números são ditos congruentes módulo $n$ se ambos têm o mesmo resto quando divididos por $n$. O resto de um número $a$ quando dividido por $n$ também é referido como o resto de $a$ módulo $n$, ou simplesmente como $a$ módulo $n$.)

Se $n$ não é primo, então, em geral, a maioria dos números $a < n$ não satisfará a relação acima. Isso leva ao seguinte algoritmo para testar primalidade: Dado um número $n$, escolha um número aleatório $a < n$ e calcule o resto de $a^n$ módulo $n$. Se o resultado não for igual a $a$, então $n$ certamente não é primo. Se for $a$, então as chances são boas de que $n$ seja primo. Agora escolha outro número aleatório $a$ e teste-o com o mesmo método. Se ele também satisfizer a equação, então podemos estar ainda mais confiantes de que $n$ é primo. Testando mais e mais valores de $a$, podemos aumentar nossa confiança no resultado. Este algoritmo é conhecido como o teste de Fermat.

Para implementar o teste de Fermat, precisamos de uma função que calcule o exponencial de um número módulo outro número:

Exemplo de Código

function expmod(base, exp, m) {
  return exp === 0
         ? 1
         : is_even(exp)
         ? square(expmod(base, exp / 2, m)) % m
         : (base * expmod(base, exp - 1, m)) % m;
}

function expmod(base, exp, m) { return exp === 0 ? 1 : is_even(exp) ? square(expmod(base, exp / 2, m)) % m : (base * expmod(base, exp - 1, m)) % m; }

⛓ sessão — este bloco compartilha o ambiente da página: as declarações dos blocos anteriores são avaliadas antes deleCódigo editável · Ctrl+Enter executa · Esc solta o foco

Isso é muito similar à função fast_expt da seção 1.2.4. Ela usa sucessivas elevações ao quadrado, de modo que o número de passos cresce logaritmicamente com o expoente.³

O teste de Fermat é realizado escolhendo aleatoriamente um número $a$ entre 1 e $n-1$ inclusive e verificando se o resto módulo $n$ da $n$-ésima potência de $a$ é igual a $a$. O número aleatório $a$ é escolhido usando a função primitiva math_random, que retorna um número não-negativo menor que 1. Portanto, para obter um número aleatório entre 1 e $n-1$, multiplicamos o valor de retorno de math_random por $n-1$, arredondamos para baixo o resultado com a função primitiva math_floor, e adicionamos 1:

Exemplo de Código

function fermat_test(n) {
  function try_it(a) {
      return expmod(a, n, n) === a;
  }
  return try_it(1 + math_floor(math_random() * (n - 1)));
}

function fermat_test(n) { function try_it(a) { return expmod(a, n, n) === a; } return try_it(1 + math_floor(math_random() * (n - 1))); }

⛓ sessão — este bloco compartilha o ambiente da página: as declarações dos blocos anteriores são avaliadas antes deleCódigo editável · Ctrl+Enter executa · Esc solta o foco

A função a seguir executa o teste um dado número de vezes, conforme especificado por um parâmetro. Seu valor é verdadeiro se o teste tiver sucesso todas as vezes, e falso caso contrário.

Exemplo de Código

function fast_is_prime(n, times) {
  return times === 0
         ? true
         : fermat_test(n)
         ? fast_is_prime(n, times - 1)
         : false;
}

function fast_is_prime(n, times) { return times === 0 ? true : fermat_test(n) ? fast_is_prime(n, times - 1) : false; }

⛓ sessão — este bloco compartilha o ambiente da página: as declarações dos blocos anteriores são avaliadas antes deleCódigo editável · Ctrl+Enter executa · Esc solta o foco

Métodos probabilísticos

O teste de Fermat difere em caráter da maioria dos algoritmos familiares, nos quais se calcula uma resposta que é garantida ser correta. Aqui, a resposta obtida é apenas provavelmente correta. Mais precisamente, se $n$ alguma vez falhar no teste de Fermat, podemos ter certeza de que $n$ não é primo. Mas o fato de que $n$ passar no teste, embora seja uma indicação extremamente forte, ainda não é uma garantia de que $n$ seja primo. O que gostaríamos de dizer é que para qualquer número $n$, se realizarmos o teste vezes suficientes e descobrirmos que $n$ sempre passa no teste, então a probabilidade de erro em nosso teste de primalidade pode ser tornada tão pequena quanto quisermos.

Infelizmente, essa afirmação não está completamente correta. Existem números que enganam o teste de Fermat: números $n$ que não são primos e ainda têm a propriedade de que $a^n$ é congruente a $a$ módulo $n$ para todos os inteiros $a < n$. Tais números são extremamente raros, então o teste de Fermat é bastante confiável na prática.⁴ Existem variações do teste de Fermat que não podem ser enganadas. Nesses testes, como no método de Fermat, testa-se a primalidade de um inteiro $n$ escolhendo um inteiro aleatório $a < n$ e verificando alguma condição que depende de $n$ e $a$. (Veja o exercício 1.28 para um exemplo de tal teste.) Por outro lado, em contraste com o teste de Fermat, pode-se provar que, para qualquer $n$, a condição não é válida para a maioria dos inteiros $a < n$ a menos que $n$ seja primo. Assim, se $n$ passar no teste para alguma escolha aleatória de $a$, as chances são maiores que 50% de que $n$ seja primo. Se $n$ passar no teste para duas escolhas aleatórias de $a$, as chances são maiores que 3 em 4 de que $n$ seja primo. Executando o teste com mais e mais valores de $a$ escolhidos aleatoriamente, podemos tornar a probabilidade de erro tão pequena quanto quisermos.

A existência de testes para os quais se pode provar que a chance de erro torna-se arbitrariamente pequena despertou interesse em algoritmos deste tipo, que vieram a ser conhecidos como algoritmos probabilísticos. Há muita atividade de pesquisa nesta área, e algoritmos probabilísticos foram frutiferamente aplicados a muitos campos.⁵

Exercício 1.21

Use a função smallest_divisor para encontrar o menor divisor de cada um dos seguintes números: 199, 1999, 19999.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Exemplo de Código

display(smallest_divisor(199));
display(smallest_divisor(1999));
smallest_divisor(19999);

display(smallest_divisor(199)); display(smallest_divisor(1999)); smallest_divisor(19999);

Código editável · Ctrl+Enter executa · Esc solta o foco

Resultados: 199 e 1999 são primos (o menor divisor é o próprio número); já 19999 = 7 × 2857, então seu menor divisor é 7.

Resolvi o exercício 1.21

Exercício 1.22

Assuma uma função primitiva get_time sem argumentos que retorna o número de milissegundos que passaram desde 00:00:00 UTC de quinta-feira, 1 de janeiro de 1970.⁶ A função timed_prime_test a seguir, quando chamada com um inteiro $n$, imprime $n$ e verifica se $n$ é primo. Se $n$ é primo, a função imprime três asteriscos seguidos pela quantidade de tempo usada para realizar o teste.

Exemplo de Código

function timed_prime_test(n) {
  display(n);
  return start_prime_test(n, get_time());
}
function start_prime_test(n, start_time) {
  return is_prime(n)
         ? report_prime(get_time() - start_time)
         : false;
}
function report_prime(elapsed_time) {
  display(" *** ");
  display(elapsed_time);
  return true;
}

function timed_prime_test(n) { display(n); return start_prime_test(n, get_time()); } function start_prime_test(n, start_time) { return is_prime(n) ? report_prime(get_time() - start_time) : false; } function report_prime(elapsed_time) { display(" *** "); display(elapsed_time); return true; }

⛓ sessão — este bloco compartilha o ambiente da página: as declarações dos blocos anteriores são avaliadas antes deleCódigo editável · Ctrl+Enter executa · Esc solta o foco

Usando esta função, escreva uma função search_for_primes que verifica a primalidade de inteiros ímpares consecutivos em um intervalo especificado. Use sua função para encontrar os três menores primos maiores que 1000; maiores que 10.000; maiores que 100.000; maiores que 1.000.000. Observe o tempo necessário para testar cada primo. Como o algoritmo de teste tem ordem de crescimento de $\Theta(\sqrt{n})$, você deve esperar que testar primos em torno de 10.000 leve cerca de $\sqrt{10}$ vezes mais tempo do que testar primos em torno de 1000. Seus dados de temporização confirmam isso? Quão bem os dados para 100.000 e 1.000.000 suportam a previsão de $\sqrt{n}$? Seu resultado é compatível com a noção de que programas em sua máquina executam em tempo proporcional ao número de passos necessários para o cálculo?

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Ideia. Caminhar só pelos ímpares, decrementando o contador a cada primo encontrado.

Exemplo de Código

function timed_prime_test(n) {
  display(n);
  return start_prime_test(n, get_time());
}
function start_prime_test(n, start_time) {
  return is_prime(n)
         ? report_prime(get_time() - start_time)
         : false;
}
function report_prime(elapsed_time) {
  display(" *** ");
  display(elapsed_time);
  return true;
}
function search_for_primes(start, count) {
  return count === 0
         ? "concluído"
         : is_even(start)
         ? search_for_primes(start + 1, count)
         : timed_prime_test(start)
         ? search_for_primes(start + 2, count - 1)
         : search_for_primes(start + 2, count);
}

search_for_primes(1000, 3);

function timed_prime_test(n) { display(n); return start_prime_test(n, get_time()); } function start_prime_test(n, start_time) { return is_prime(n) ? report_prime(get_time() - start_time) : false; } function report_prime(elapsed_time) { display(" *** "); display(elapsed_time); return true; } function search_for_primes(start, count) { return count === 0 ? "concluído" : is_even(start) ? search_for_primes(start + 1, count) : timed_prime_test(start) ? search_for_primes(start + 2, count - 1) : search_for_primes(start + 2, count); } search_for_primes(1000, 3);

Código editável · Ctrl+Enter executa · Esc solta o foco

Os primos: 1009, 1013, 1019; 10007, 10009, 10037; 100003, 100019, 100043; 1000003, 1000033, 1000037.

Sobre os tempos. Em máquinas atuais, todos esses testes levam praticamente 0 ms — o exercício foi escrito quando computadores eram milhões de vezes mais lentos. Para ver a razão $\sqrt{10} \approx 3{,}16$, procure primos perto de $10^{10}$, $10^{11}$ e $10^{12}$ (ainda dentro da precisão dos números de JavaScript, $2^{53}$): as razões entre tempos consecutivos se aproximam de $\sqrt{10}$, confirmando que o tempo de execução acompanha o número de passos, $\Theta(\sqrt n)$.

Resolvi o exercício 1.22

Exercício 1.23

A função smallest_divisor mostrada no início desta seção faz muitos testes desnecessários: Depois que ela verifica se o número é divisível por 2, não há sentido em verificar se ele é divisível por qualquer número par maior. Isso sugere que os valores usados para test_divisor não deveriam ser 2, 3, 4, 5, 6, ... mas sim 2, 3, 5, 7, 9, ... Para implementar esta mudança, declare uma função next que retorna 3 se sua entrada for igual a 2 e caso contrário retorna sua entrada mais 2. Modifique a função smallest_divisor para usar next(test_divisor) em vez de test_divisor + 1. Com timed_prime_test incorporando esta versão modificada de smallest_divisor, execute o teste para cada um dos 12 primos encontrados no exercício 1.22. Como esta modificação reduz pela metade o número de passos de teste, você deve esperar que execute cerca de duas vezes mais rápido. Esta expectativa é confirmada? Se não, qual é a razão observada das velocidades dos dois algoritmos, e como você explica o fato de que ela é diferente de 2?

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Exemplo de Código

function next(n) {
  return n === 2 ? 3 : n + 2;
}
function find_divisor(n, test_divisor) {
  return square(test_divisor) > n
         ? n
         : divides(test_divisor, n)
         ? test_divisor
         : find_divisor(n, next(test_divisor));
}
function smallest_divisor(n) {
  return find_divisor(n, 2);
}
function is_prime(n) {
  return n === smallest_divisor(n);
}

is_prime(1000037);

function next(n) { return n === 2 ? 3 : n + 2; } function find_divisor(n, test_divisor) { return square(test_divisor) > n ? n : divides(test_divisor, n) ? test_divisor : find_divisor(n, next(test_divisor)); } function smallest_divisor(n) { return find_divisor(n, 2); } function is_prime(n) { return n === smallest_divisor(n); } is_prime(1000037);

Código editável · Ctrl+Enter executa · Esc solta o foco

A expectativa se confirma? Só em parte. Metade dos candidatos é testada, mas cada passo ficou mais caro: next é uma chamada de função com um teste condicional, no lugar de uma soma direta. Na prática a razão observada fica tipicamente entre 1,5 e 2 — o número de passos caiu pela metade, mas passos não têm todos o mesmo custo. É um bom lembrete de que $\Theta$ esconde constantes que a medição revela.

Resolvi o exercício 1.23

Exercício 1.24

Modifique a função timed_prime_test do exercício 1.22 para usar fast_is_prime (o método de Fermat), e teste cada um dos 12 primos que você encontrou naquele exercício. Como o teste de Fermat tem crescimento $\Theta(\log n)$, como você esperaria que o tempo para testar primos perto de 1.000.000 se comparasse com o tempo necessário para testar primos perto de 1000? Seus dados confirmam isso? Você pode explicar qualquer discrepância que encontrar?

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Ideia. Trocar is_prime por fast_is_prime (teste de Fermat) na mesma estrutura de medição:

Exemplo de Código

function expmod(base, exp, m) {
  return exp === 0
         ? 1
         : is_even(exp)
         ? square(expmod(base, exp / 2, m)) % m
         : (base * expmod(base, exp - 1, m)) % m;
}
function fermat_test(n) {
  function try_it(a) {
      return expmod(a, n, n) === a;
  }
  return try_it(1 + math_floor(math_random() * (n - 1)));
}
function fast_is_prime(n, times) {
  return times === 0
         ? true
         : fermat_test(n)
         ? fast_is_prime(n, times - 1)
         : false;
}

display(fast_is_prime(1009, 10));
fast_is_prime(1000037, 10);

function expmod(base, exp, m) { return exp === 0 ? 1 : is_even(exp) ? square(expmod(base, exp / 2, m)) % m : (base * expmod(base, exp - 1, m)) % m; } function fermat_test(n) { function try_it(a) { return expmod(a, n, n) === a; } return try_it(1 + math_floor(math_random() * (n - 1))); } function fast_is_prime(n, times) { return times === 0 ? true : fermat_test(n) ? fast_is_prime(n, times - 1) : false; } display(fast_is_prime(1009, 10)); fast_is_prime(1000037, 10);

Código editável · Ctrl+Enter executa · Esc solta o foco

Expectativa. Com crescimento $\Theta(\log n)$, testar primos perto de $1.000.000$ deveria custar cerca de o dobro de testar perto de $1.000$ ($\log 10^6 = 2 \log 10^3$). Na prática a razão medida costuma ficar perto disso, mas não exatamente: o custo de cada multiplicação não é constante, o número de repetições do teste e o gerador aleatório adicionam ruído, e para números tão pequenos o tempo é dominado por sobrecustos fixos do interpretador.

Resolvi o exercício 1.24

Exercício 1.25

Alyssa P. Hacker reclama que fizemos muito trabalho extra ao escrever expmod. Afinal, ela diz, já que já sabemos como calcular exponenciais, poderíamos ter simplesmente escrito

function expmod(base, exp, m) {
    return fast_expt(base, exp) % m;
}

Ela está correta? Esta função serviria tão bem para nosso testador de primos rápido? Explique.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Alyssa está errada — a função dela é matematicamente correta, mas inútil na prática.

expmod reduz módulo m a cada passo, então os números intermediários nunca passam de $m^2$. A versão de Alyssa calcula primeiro $b^e$ por inteiro: para um teste de Fermat com $n$ perto de um milhão, isso é um número com milhões de dígitos. Em uma linguagem com inteiros exatos, isso torna cada multiplicação lentíssima; em JavaScript é pior — números perdem precisão acima de $2^{53}$ e viram Infinity por volta de $10^{308}$, então o resultado do % final é simplesmente errado. Experimente: fast_expt(999999, 999999) é Infinity, e Infinity % m é NaN.

A lição é a da nota de rodapé 3: reduzir módulo $m$ cedo e sempre não é uma otimização opcional — é o que mantém o cálculo dentro do mundo dos números representáveis.

Resolvi o exercício 1.25

Exercício 1.26

Louis Reasoner está tendo grande dificuldade com o exercício 1.24. Seu teste fast_is_prime parece executar mais lentamente do que seu teste is_prime. Louis chama sua amiga Eva Lu Ator para ajudar. Quando eles examinam o código de Louis, descobrem que ele reescreveu a função expmod para usar uma multiplicação explícita, em vez de chamar square:

function expmod(base, exp, m) {
    return exp === 0
           ? 1
           : is_even(exp)
           ? (  expmod(base, exp / 2, m)
              * expmod(base, exp / 2, m)) % m
           : (base * expmod(base, exp - 1, m)) % m;
}

"Não vejo que diferença isso poderia fazer", diz Louis. "Eu vejo", diz Eva. "Ao escrever a função dessa forma, você transformou o processo $\Theta(\log n)$ em um processo $\Theta(n)$." Explique.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Na versão de Louis, o argumento de square virou duas chamadas idênticas: cada nível de recursão com expoente par dispara duas subárvores completas em vez de uma. A recursão que antes era uma corrente de comprimento $\log n$ virou uma árvore binária de profundidade $\log n$ — e uma árvore binária com essa profundidade tem da ordem de $2^{\log_2 n} = n$ nós.

Formalmente: $T(e) = 2\,T(e/2) + \Theta(1)$ resolve para $T(e) = \Theta(e)$, enquanto com square era $T(e) = T(e/2) + \Theta(1) = \Theta(\log e)$. A avaliação em ordem aplicativa avalia o operando uma vez quando ele é argumento de square, mas avalia as duas ocorrências quando Louis as escreve explicitamente.

Resolvi o exercício 1.26

Exercício 1.27

Demonstre que os números de Carmichael listados na nota de rodapé 4 realmente enganam o teste de Fermat. Isto é, escreva uma função que recebe um inteiro $n$ e testa se $a^n$ é congruente a $a$ módulo $n$ para todo $a < n$, e tente sua função nos números de Carmichael dados.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Ideia. Testar a congruência $a^n \equiv a \pmod n$ para todos os $a < n$:

Exemplo de Código

function expmod(base, exp, m) {
  return exp === 0
         ? 1
         : is_even(exp)
         ? square(expmod(base, exp / 2, m)) % m
         : (base * expmod(base, exp - 1, m)) % m;
}
function fools_fermat(n) {
  function test_all(a) {
      return a >= n
             ? true
             : expmod(a, n, n) === a % n
             ? test_all(a + 1)
             : false;
  }
  return test_all(1);
}

display(fools_fermat(561));
display(fools_fermat(1105));
display(fools_fermat(1729));
fools_fermat(15);

function expmod(base, exp, m) { return exp === 0 ? 1 : is_even(exp) ? square(expmod(base, exp / 2, m)) % m : (base * expmod(base, exp - 1, m)) % m; } function fools_fermat(n) { function test_all(a) { return a >= n ? true : expmod(a, n, n) === a % n ? test_all(a + 1) : false; } return test_all(1); } display(fools_fermat(561)); display(fools_fermat(1105)); display(fools_fermat(1729)); fools_fermat(15);

Código editável · Ctrl+Enter executa · Esc solta o foco

Resultado. Os números de Carmichael 561, 1105 e 1729 passam no teste para todas as bases — indistinguíveis de primos aos olhos de Fermat — enquanto um composto comum como 15 falha imediatamente. (O 1729 é o famoso "número de táxi" de Hardy e Ramanujan.)

Resolvi o exercício 1.27

Exercício 1.28

Uma variante do teste de Fermat que não pode ser enganada é chamada de teste de Miller-Rabin (Miller 1976; Rabin 1980). Este começa de uma forma alternativa do Pequeno Teorema de Fermat, que afirma que se $n$ é um número primo e $a$ é qualquer inteiro positivo menor que $n$, então $a$ elevado à $(n-1)$-ésima potência é congruente a 1 módulo $n$. Para testar a primalidade de um número $n$ pelo teste de Miller-Rabin, escolhemos um número aleatório $a < n$ e elevamos $a$ à $(n-1)$-ésima potência módulo $n$ usando a função expmod. No entanto, sempre que realizamos o passo de elevação ao quadrado em expmod, verificamos se descobrimos uma "raiz quadrada não trivial de 1 módulo $n$", isto é, um número diferente de 1 ou $n-1$ cujo quadrado é igual a 1 módulo $n$. É possível provar que se tal raiz quadrada não trivial de 1 existir, então $n$ não é primo. Também é possível provar que se $n$ é um número ímpar que não é primo, então, para pelo menos metade dos números $a < n$, calcular $a^{n-1}$ desta forma revelará uma raiz quadrada não trivial de 1 módulo $n$. (É por isso que o teste de Miller-Rabin não pode ser enganado.) Modifique a função expmod para sinalizar se ela descobrir uma raiz quadrada não trivial de 1, e use isso para implementar o teste de Miller-Rabin com uma função análoga a fermat_test. Verifique sua função testando vários primos e não-primos conhecidos. Dica: Uma maneira conveniente de fazer expmod sinalizar é fazê-la retornar 0.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Ideia. No passo de elevação ao quadrado, sinalizar (retornando 0) quando encontramos uma raiz quadrada não trivial de 1 módulo $n$ — um $x \neq 1, n-1$ com $x^2 \equiv 1 \pmod n$:

Exemplo de Código

function square_check(x, m) {
  return x !== 1 && x !== m - 1 && (x * x) % m === 1
         ? 0
         : (x * x) % m;
}
function expmod(base, exp, m) {
  return exp === 0
         ? 1
         : is_even(exp)
         ? square_check(expmod(base, exp / 2, m), m)
         : (base * expmod(base, exp - 1, m)) % m;
}
function miller_rabin_test(n) {
  function try_it(a) {
      return expmod(a, n - 1, n) === 1;
  }
  return try_it(2 + math_floor(math_random() * (n - 3)));
}
function fast_is_prime(n, times) {
  return times === 0
         ? true
         : miller_rabin_test(n)
         ? fast_is_prime(n, times - 1)
         : false;
}

display(fast_is_prime(1009, 20));   // primo
display(fast_is_prime(561, 20));    // Carmichael!
display(fast_is_prime(6601, 20));   // Carmichael!
fast_is_prime(1000037, 20);

function square_check(x, m) { return x !== 1 && x !== m - 1 && (x * x) % m === 1 ? 0 : (x * x) % m; } function expmod(base, exp, m) { return exp === 0 ? 1 : is_even(exp) ? square_check(expmod(base, exp / 2, m), m) : (base * expmod(base, exp - 1, m)) % m; } function miller_rabin_test(n) { function try_it(a) { return expmod(a, n - 1, n) === 1; } return try_it(2 + math_floor(math_random() * (n - 3))); } function fast_is_prime(n, times) { return times === 0 ? true : miller_rabin_test(n) ? fast_is_prime(n, times - 1) : false; } display(fast_is_prime(1009, 20)); // primo display(fast_is_prime(561, 20)); // Carmichael! display(fast_is_prime(6601, 20)); // Carmichael! fast_is_prime(1000037, 20);

Código editável · Ctrl+Enter executa · Esc solta o foco

Por que funciona. O 0 é "pegajoso": uma vez sinalizado, propaga-se até o topo (qualquer coisa ao quadrado ou multiplicada módulo $m$ continua 0) e faz expmod(a, n-1, n) === 1 falhar. Note os números de Carmichael que enganavam Fermat no exercício 1.27 sendo desmascarados — como pelo menos metade das bases revela uma raiz não trivial quando $n$ é composto, vinte rodadas dão confiança de mais de $1 - 2^{-20}$.

Resolvi o exercício 1.28

---

Notas de Rodapé

1 Se $d$ é um divisor de $n$, então também é $n/d$. Mas $d$ e $n/d$ não podem ambos ser maiores que $\sqrt{n}$.

2 Pierre de Fermat (1601–1665) é considerado o fundador da teoria dos números moderna. Ele obteve muitos resultados importantes em teoria dos números, mas geralmente anunciava apenas os resultados, sem fornecer suas provas. O Pequeno Teorema de Fermat foi declarado em uma carta que ele escreveu em 1640. A primeira prova publicada foi dada por Euler em 1736 (e uma prova anterior idêntica foi descoberta nos manuscritos não publicados de Leibniz). O mais famoso dos resultados de Fermat — conhecido como Último Teorema de Fermat — foi anotado em 1637 em sua cópia do livro Aritmética (do matemático grego do terceiro século Diofanto) com a observação "Descobri uma prova verdadeiramente notável, mas esta margem é muito pequena para contê-la." Encontrar uma prova do Último Teorema de Fermat tornou-se um dos desafios mais famosos da teoria dos números. Uma solução completa foi finalmente dada em 1995 por Andrew Wiles da Universidade de Princeton.

3 Os passos de redução nos casos onde o expoente $e$ é maior que 1 são baseados no fato de que, para quaisquer inteiros $x$, $y$ e $m$, podemos encontrar o resto de $x$ vezes $y$ módulo $m$ calculando separadamente os restos de $x$ módulo $m$ e $y$ módulo $m$, multiplicando-os, e então tomando o resto do resultado módulo $m$. Por exemplo, no caso onde $e$ é par, calculamos o resto de $b^{e/2}$ módulo $m$, elevamos ao quadrado, e tomamos o resto módulo $m$. Esta técnica é útil porque significa que podemos realizar nosso cálculo sem nunca ter que lidar com números muito maiores que $m$. (Compare o exercício 1.25.)

4 Números que enganam o teste de Fermat são chamados números de Carmichael, e pouco se sabe sobre eles além de que são extremamente raros. Existem 255 números de Carmichael abaixo de 100.000.000. Os primeiros poucos são 561, 1105, 1729, 2465, 2821 e 6601. Ao testar a primalidade de números muito grandes escolhidos aleatoriamente, a chance de tropeçar em um valor que engana o teste de Fermat é menor que a chance de que radiação cósmica faça o computador cometer um erro ao executar um algoritmo "correto". Considerar um algoritmo inadequado pela primeira razão, mas não pela segunda, ilustra a diferença entre matemática e engenharia.

5 Uma das aplicações mais marcantes do teste de primalidade probabilística tem sido para o campo da criptografia. Embora seja computacionalmente inviável fatorar um número arbitrário de 300 dígitos no momento desta escrita (2021), a primalidade de tal número pode ser verificada em alguns segundos com o teste de Fermat. Este fato forma a base de uma técnica para construir "códigos inquebráveis" sugerida por Rivest, Shamir e Adleman (1977). O algoritmo RSA resultante tornou-se uma técnica amplamente usada para aumentar a segurança das comunicações eletrônicas. Por causa deste e desenvolvimentos relacionados, o estudo de números primos, uma vez considerado o epítome de um tópico em matemática "pura" a ser estudado apenas por si próprio, agora se revela ter aplicações práticas importantes para criptografia, transferência eletrônica de fundos e recuperação de informações.

6 Esta data é chamada de época UNIX e faz parte da especificação de funções que lidam com tempo no sistema operacional UNIX™.

📝 Encontrou algo errado nesta página?

Sua ajuda é muito importante para melhorar a qualidade da tradução!

🐛 Encontrou um erro?

Se você encontrou:

• Erro de tradução (palavra incorreta, termo técnico errado)
• Erro de ortografia ou gramática
• Link quebrado
• Código de exemplo que não funciona
• Problema de formatação

Reporte um bug →

❓ Tem uma dúvida?

Se você tem:

• Dúvida sobre o conteúdo desta seção
• Pergunta sobre um conceito do SICP
• Dificuldade em entender algum exemplo
• Questão sobre a tradução de algum termo

Inicie uma discussão →

💡 Tem uma sugestão de melhoria?

Se você quer sugerir:

• Melhoria na explicação
• Exemplo adicional
• Recurso visual (diagrama, ilustração)
• Qualquer outra ideia

Sugira uma melhoria →

🌍 Quer discutir a tradução?

Se você quer debater:

• Escolha de tradução de algum termo
• Consistência de terminologia
• Nuances do português

Discussão de tradução →

Obrigado por ajudar a melhorar o SICP.js PT-BR! ✨