Metodo di fattorizzazione di Fermat

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica wikitesto]

  1. Sia n un intero dispari.
  2. (dove indica la funzione parte intera superiore).
  3. Ripeti
    1. se non è un quadrato perfetto allora
  4. finché non è un quadrato perfetto.

Spiegazione[modifica | modifica wikitesto]

Supponiamo che n sia un intero dispari, e che esistano due interi a e b tali che n=ab (con a>b). Allora

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 può quindi essere vista come , e, se , si è ottenuta una fattorizzazione non banale di n.

L'algoritmo consiste quindi nel calcolare i numeri finché non si trova un quadrato perfetto; in tal caso

Il calcolo dei quadrati successivi è inoltre facilitato dal fatto che le differenze tra quadrati consecutivi formato una progressione aritmetica di ragione 2: . 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[modifica | modifica wikitesto]

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 , si potevano invece cercare questi in modo che n dividesse la differenza tra i quadrati, ovvero cercare soluzioni della congruenza

o equivalentemente

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.

Bibliografia[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

Matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica