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. a=\lceil\sqrt{n}\rceil (dove \lceil \cdot \rceil indica la funzione parte intera superiore).
  3. Ripeti
    1. b_2=a^2-n
    2. se b_2 non è un quadrato perfetto allora a=a+1
  4. finché b_2 non è un quadrato perfetto.
  5. b= \sqrt{b_2}
  6. n=(a-b)(a+b)

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

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[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 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.

Bibliografia[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

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