Calculadora de Fatoração de Fermat

Sobre esta calculadora

O método de fatoração de Fermat explora o fato de que qualquer inteiro ímpar N pode ser escrito como uma diferença de dois quadrados, N = a² − b² = (a−b)(a+b). O algoritmo começa em a = ⌈√N⌉ e aumenta a de 1 em 1 a cada passo, verificando se a² − N é, ele próprio, um quadrado perfeito (b²); no momento em que for, N se fatora imediatamente em (a−b)(a+b). Esta calculadora executa esse laço e mostra cada passo dado para encontrar os fatores.

O método converge em pouquíssimos passos quando os dois fatores de N estão próximos — sua principal fraqueza é também seu uso real mais importante: estudantes de criptografia e pesquisadores de segurança usam a fatoração de Fermat para demonstrar por que os módulos RSA devem ser construídos a partir de primos bem afastados entre si, já que primos escolhidos muito próximos tornam o módulo trivialmente quebrável. Também é um exercício padrão em cursos de teoria dos números para ilustrar o raciocínio da diferença de quadrados.