Metodo di fattorizzazione di Fermat
# 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.

