title: Metodo di fattorizzazione di Fermat
text: # Metodo di fattorizzazione di Fermat
  
  Il metodo di fattorizzazione di Fermat è un algoritmo ideato da Pierre de Fermat per fattorizzare dei numeri interi nei suoi fattori primi. Si basa sulla rappresentazione di un numero come differenza tra due quadrati, ed è più efficace quando esistono due fattori del numero vicini tra loro.
  
  ## Algoritmo
  
  * Sia n un intero dispari.
  * $a=\lceil {\sqrt {n}}\rceil$ (dove $\lceil \cdot \rceil$ indica la funzione parte intera superiore).
  * Ripeti
     * $b_{2}=a^{2}-n$
     * se $b_{2}$ non è un quadrato perfetto allora $a=a+1$
  * finché $b_{2}$ non è un quadrato perfetto.
  * $b={\sqrt {b_{2}}}$
  * $n=(a-b)(a+b)$
  
  ## Spiegazione
  
  Supponiamo che n sia un intero dispari, e che esistano due interi a e b tali che n=ab (con a>b). Allora
  
      $n=\left({\frac {a+b}{2}}\right)^{2}-\left({\frac {a-b}{2}}\right)^{2}$
  
  Quindi n è la differenza di due quadrati. Essendo n un intero dispari, anche a e b lo devono essere a loro volta: dunque i numeri d=a+b e c=a-b sono pari e la loro semisomma è un intero. L'espressione $d^{2}-c^{2}$ può quindi essere vista come $(d-c)(d+c)$, e, se $d\neq c+1$, si è ottenuta una fattorizzazione non banale di n.
  
  L'algoritmo consiste quindi nel calcolare i numeri $a^{2}-n$ finché non si trova un quadrato perfetto; in tal caso
  
      $a^{2}-n=b^{2}\Leftrightarrow a^{2}-b^{2}=n$
  
  Il calcolo dei quadrati successivi è inoltre facilitato dal fatto che le differenze tra quadrati consecutivi formato una progressione aritmetica di ragione 2: $(a+i)^{2}-(a+i-1)^{2}=2a+2i+1$. Il riconoscimento dei quadrati può essere effettuato o attraverso metodi di aritmetica modulare (che elimina molte possibilità per i quadrati: ad esempio l'ultima cifra decimale non può essere solo 2, 3, 7 o 8) oppure attraverso apposite tavole dei quadrati.
  
  ## Generalizzazioni
  
  Nel Novecento sono stati proposti diversi algoritmi di fattorizzazione che si basavano su quello di Fermat. Maurice Kraitchik suggerì negli anni Venti che, invece di considerare interi x e y tali che $n=x^{2}-y^{2}$, si potevano invece cercare questi in modo che n dividesse la differenza tra i quadrati, ovvero cercare soluzioni della congruenza
  
      $x^{2}-y^{2}\equiv 0\mod n$
  
  o equivalentemente
  
      $x^{2}\equiv y^{2}\mod n$
  
  In questo contesto, le soluzioni "interessanti" della congruenza sono quelle in cui x non è congruo né a y né a -y modulo n e in cui entrambi x e y sono coprimi con n. Se n è dispari e divisibile per almeno due primi, si è dimostrato che almeno metà delle soluzioni sono interessanti. In questo caso |x-y| è compreso strettamente tra 1 ed n, e quindi è un fattore non banale di n.
  
  Su questa idea si basano sia l'algoritmo delle frazioni continue che il crivello quadratico.
  
  