Calculadora de factorització de Fermat

Sobre aquesta calculadora

El mètode de factorització de Fermat aprofita el fet que qualsevol enter senar N es pot escriure com una diferència de dos quadrats, N = a² − b² = (a−b)(a+b). L'algorisme comença en a = ⌈√N⌉ i augmenta a en 1 a cada pas, comprovant si a² − N és ell mateix un quadrat perfecte (b²); en el moment que ho és, N es factoritza immediatament com (a−b)(a+b). Aquesta calculadora executa aquest bucle i mostra tots els passos que ha fet per trobar els factors.

El mètode convergeix en molt pocs passos quan els dos factors de N són propers: la seva principal debilitat és també el seu ús més important al món real. Els estudiants de criptografia i els investigadors de seguretat fan servir la factorització de Fermat per demostrar per què els mòduls RSA s'han de construir amb primers que estiguin allunyats, ja que uns primers triats massa propers fan que el mòdul sigui trivialment vulnerable. També és un exercici estàndard dels cursos de teoria de nombres per il·lustrar el raonament de la diferència de quadrats.