Fatorar um número inteiro significa encontrar os fatores primos deste.

Exemplos: 15 = 3*5, ou 187 = 11*17

A fatoração tem duas características: é difícil de fazer, mas é fácil de checar se uma solução é válida.

Exemplo: Quais os fatores primos de 3127?

Um método possível para encontrar os fatores do número N é testar todas as alternativas até raiz(N). Ou seja, dividir 3127 por 2, 3, 5, 7, 9, até raiz(3127) ~= 55.

Com isso, chegamos que 3127 = 53*59. E é fácil checar que 59 é um dos fatores de 3127, basta fazer a divisão.

A fatoração de números inteiros (ou melhor, a dificuldade em fazê-lo) é a base de toda a criptografia moderna.

O número grande (digamos 3127) é a minha chave pública com a qual o emissor da informação faz a codificação. Para decodificar, preciso da chave privada (53 e 59). E a segurança baseia-se…