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

  1. Sia n un intero dispari.
  2. a = ⌈ n ⌉ {\displaystyle a=\lceil {\sqrt {n}}\rceil } (dove ⌈ ⋅ ⌉ {\displaystyle \lceil \cdot \rceil } indica la funzione parte intera superiore).
  3. Ripeti
    1. b 2 = a 2 − n {\displaystyle b_{2}=a^{2}-n}
    2. se b 2 {\displaystyle b_{2}} non è un quadrato perfetto allora a = a + 1 {\displaystyle a=a+1}
  4. finché b 2 {\displaystyle b_{2}} non è un quadrato perfetto.
  5. b = b 2 {\displaystyle b={\sqrt {b_{2}}}}
  6. n = ( a − b ) ( a + b ) {\displaystyle 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 = ( a + b 2 ) 2 − ( a − b 2 ) 2 {\displaystyle 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 {\displaystyle d^{2}-c^{2}} può quindi essere vista come ( d − c ) ( d + c ) {\displaystyle (d-c)(d+c)} , e, se d ≠ c + 1 {\displaystyle d\neq c+1} , si è ottenuta una fattorizzazione non banale di n.

L'algoritmo consiste quindi nel calcolare i numeri a 2 − n {\displaystyle a^{2}-n} finché non si trova un quadrato perfetto; in tal caso

a 2 − n = b 2 ⇔ a 2 − b 2 = n {\displaystyle 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 = 2 a + 2 i + 1 {\displaystyle (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 {\displaystyle 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 ≡ 0 mod n {\displaystyle x^{2}-y^{2}\equiv 0\mod n}

o equivalentemente

x 2 ≡ y 2 mod n {\displaystyle 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

  • Keith Devlin, Dove va la matematica. Bollati Boringhieri, Torino, 1994. ISBN 88-339-1182-9
  • Harold Davenport, Aritmetica superiore. Zanichelli, Bologna, 1994. ISBN 88-08-09154-6

Collegamenti esterni

  • (EN) Eric W. Weisstein, Metodo di fattorizzazione di Fermat, su MathWorld, Wolfram Research. Modifica su Wikidata
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica