Calculadora de fatoração em números primos

O que é a fatoração em primos?

Todo o número inteiro maior do que um ou é primo — divisível apenas por si e por um — ou é um produto de primos, e esse produto é único a menos da ordem por que o escreva. É o teorema fundamental da aritmética, e fatorizar é encontrá-lo: 360 é 2 × 2 × 2 × 3 × 3 × 5, que se escreve 2³ × 3² × 5, e nenhuma outra combinação de primos dá 360.

É a operação que está por baixo de boa parte da aritmética corrente. Simplificar uma fração é cortar fatores primos comuns. Um mínimo denominador comum constrói-se com os primos de cada denominador, tomando a maior potência de cada um. E o número de divisores sai diretamente da fatoração: multiplique cada expoente mais um, portanto 360 = 2³ × 3² × 5¹ tem 4 × 3 × 2 = 24 divisores, e a ferramenta lista-os todos.

Esta calculadora trabalha em aritmética inteira exata e não em vírgula flutuante, portanto não há um tamanho a partir do qual as respostas passem a ser aproximadas em silêncio. Cole um número de quarenta algarismos e cada fator que devolver estará exatamente certo.

Como usar

1. Escreva ou cole um número inteiro. Vírgulas, espaços e sublinhados são ignorados, portanto um número copiado de uma folha de cálculo funciona tal como está. Decimais, sinal de menos e notação exponencial são recusados em vez de reinterpretados em silêncio.
2. Leia a fatoração e os divisores. Os números compostos aparecem em forma exponencial com todos os fatores primos, mais a contagem de divisores e, quando a lista tem comprimento razoável, todos os divisores. Um número primo é simplesmente indicado como primo.
3. Se disser que não terminou, acredite. Os números difíceis atingem um limite de trabalho e a ferramenta di-lo, mostrando o que encontrou e o que sobra. O botão oferece uma procura mais longa; se essa também falhar, o número está mesmo além do que um navegador consegue em tempo razoável.

Porque alguns números a travam, e porque é isso o essencial

Fatorizar é imensamente mais fácil para uns números do que para outros, e a diferença não está no tamanho. Ir tirando primos pequenos resolve a maioria num instante, porque a maioria dos números tem um fator pequeno: sobre quarenta números aleatórios de quarenta algarismos, o do meio fatoriza-se em cerca de um sexto de segundo. O difícil é um número sem fator pequeno nenhum: um semiprimo, o produto de dois primos grandes e mais nada.

O método ingénuo torna isto evidente. A divisão por tentativa experimenta todos os candidatos até à raiz quadrada, portanto o seu custo duplica mais ou menos a cada dois algarismos: na máquina onde esta página foi construída, um semiprimo de dois primos de dez algarismos demorou três segundos, e um de dois primos de onze algarismos demorou três minutos e meio. Esta ferramenta usa antes o rho de Pollard, que levou esse mesmo caso de onze algarismos de 212 segundos para 68 milissegundos — três ordens de grandeza, com um algoritmo que cabe em vinte linhas.

Mas o rho só desloca o muro, não o remove. Um semiprimo de dois primos de treze algarismos continua fora do alcance de um separador do navegador, e isso não é um defeito de que pedir desculpa. É a própria base da criptografia de chave pública: as chaves RSA são semiprimos escolhidos precisamente porque multiplicar dois primos grandes é trivial e desfazê-lo não é. Os números que protegem o seu banco têm a mesma forma daquele em que esta página desiste, apenas muitíssimo maiores.

É por isso que o limite aqui é um orçamento de trabalho e não um teto de algarismos. Um teto de algarismos erraria nas duas direções: recusaria o número de quarenta algarismos que se fatoriza num milissegundo e aceitaria o de vinte e cinco que demora segundos. Contar o esforço significa que a ferramenta pára quando o trabalho se torna desmedido, seja qual for o aspeto do número, e reporta com honestidade em vez de congelar o separador.

Limites honestos

Quando a procura pára antes do tempo, tudo o que aparece continua verdadeiro. Os fatores encontrados são mesmo fatores primos do seu número; o que resta simplesmente não foi decomposto. Multiplique os fatores mostrados pelo resto e recupera o seu número exatamente — essa propriedade vale com qualquer orçamento, e é o que os testes verificam com mais insistência, porque uma resposta parcial que se faz passar por completa é muito pior do que uma que admite ter parado.

A primalidade é decidida pelo teste de Miller-Rabin com um conjunto fixo de doze testemunhas. Essa combinação está provada correta para todo o número abaixo de cerca de 3,3 × 10²⁴, o que cobre tudo o que esta ferramenta há de receber na prática; acima disso passa a ser um teste probabilístico em vez de uma prova, e a hipótese de erro é ínfima mas não nula. Quase nenhuma calculadora diz de que lado dessa linha está.

O zero e o um têm respostas próprias em vez de um resultado vazio. O zero não tem fatoração, porque todos os números o dividem. O um não é primo nem composto — não tem fator primo nenhum —, o que é um facto sobre a definição e não um descuido, e a razão por que o teorema fundamental começa no dois.

A lista de divisores é limitada no ecrã, porque um número muito composto pode ter milhares e mostrá-los todos não ajuda ninguém. A contagem por cima é sempre o total verdadeiro, calculado a partir dos expoentes e não por contagem do que se vê.

Porque é grátis

Porque não custa nada manter. Toda a aritmética acontece no seu navegador com o suporte nativo de inteiros grandes — nada é enviado, nenhum servidor vê os seus números, e não há conta nem limite de quantos verifica.

O motor é confrontado com um fatorizador escrito de forma independente noutra linguagem, e com algo mais forte do que qualquer implementação de referência: uma fatoração verifica-se multiplicando-a de volta, e os testes fazem-no com todos os orçamentos de trabalho até zero. Dois dos defeitos que essa verificação apanhou eram precisamente dos perigosos: uma resposta parcial apresentada como completa, e um resto declarado primo.