Metoda de factorizare a lui Fermat

Metoda factorizarea lui Fermat este un algoritm conceput de Pierre de Fermat a factorului numere întregi în lor factori de prim . Se bazează pe reprezentarea unui număr ca diferență între două pătrate și este cel mai eficient atunci când există doi factori ai numărului care sunt apropiați unul de celălalt.

Algoritm

Fie n un număr întreg ciudat.
$a=\lceil {\sqrt {n}}\rceil$ ${\ displaystyle a = \ lceil {\ sqrt {n}} \ rceil}$ ${\ displaystyle a = \ lceil {\ sqrt {n}} \ rceil}$ (unde este $\lceil \cdot \rceil$ ${\ displaystyle \ lceil \ cdot \ rceil}$ ${\ displaystyle \ lceil \ cdot \ rceil}$ indică funcția de număr întreg de sus).
Repeta
1. $b_{2}=a^{2}-n$ ${\ displaystyle b_ {2} = a ^ {2} -n}$ ${\ displaystyle b_ {2} = a ^ {2} -n}$
2. de sine $b_{2}$ ${\ displaystyle b_ {2}}$ $b_ {2}$ atunci nu este un pătrat perfect $a=a+1$ ${\ displaystyle a = a + 1}$ ${\ displaystyle a = a + 1}$
atata timp cat $b_{2}$ ${\ displaystyle b_ {2}}$ $b_ {2}$ nu este un pătrat perfect.
$b={\sqrt {b_{2}}}$ ${\ displaystyle b = {\ sqrt {b_ {2}}}}$ ${\ displaystyle b = {\ sqrt {b_ {2}}}}$
$n=(a-b)(a+b)$ ${\ displaystyle n = (ab) (a + b)}$ ${\ displaystyle n = (a-b) (a + b)}$

Explicaţie

Să presupunem că n este un număr întreg impar și că există două numere întregi a și b astfel încât n = ab (cu a > b ). Atunci

n=\left({\frac {a+b}{2}}\right)^{2}-\left({\frac {a-b}{2}}\right)^{2}

{\ displaystyle n = \ left ({\ frac {a + b} {2}} \ right) ^ {2} - \ left ({\ frac {ab} {2}} \ right) ^ {2}}

{\ displaystyle n = \ left ({\ frac {a + b} {2}} \ right) ^ {2} - \ left ({\ frac {a-b} {2}} \ right) ^ {2}}

Deci n este diferența dintre două pătrate. Deoarece n este un număr întreg ciudat, a și b trebuie să fie și ele la rândul lor: prin urmare, numerele d = a + b și c = ab sunt pare, iar jumătatea lor este un număr întreg. Expresia $d^{2}-c^{2}$ ${\ displaystyle d ^ {2} -c ^ {2}}$ ${\ displaystyle d ^ {2} -c ^ {2}}$ poate fi deci văzut ca $(d-c)(d+c)$ ${\ displaystyle (dc) (d + c)}$ ${\ displaystyle (d-c) (d + c)}$ , si daca $d\neq c+1$ ${\ displaystyle d \ neq c + 1}$ ${\ displaystyle d \ neq c + 1}$ , o factorizare non-banală a lui n .

Prin urmare, algoritmul constă în calcularea numerelor $a^{2}-n$ ${\ displaystyle a ^ {2} -n}$ ${\ displaystyle a ^ {2} -n}$ până când se găsește un pătrat perfect; atunci

a^{2}-n=b^{2}\Leftrightarrow a^{2}-b^{2}=n

{\ displaystyle a ^ {2} -n = b ^ {2} \ Leftrightarrow a ^ {2} -b ^ {2} = n}

{\ displaystyle a ^ {2} -n = b ^ {2} \ Leftrightarrow a ^ {2} -b ^ {2} = n}

Calculul pătratelor succesive este facilitat în continuare de faptul că diferențele dintre pătratele consecutive au format o progresie aritmetică a rațiunii 2: $(a+i)^{2}-(a+i-1)^{2}=2a+2i+1$ ${\ displaystyle (a + i) ^ {2} - (a + i-1) ^ {2} = 2a + 2i + 1}$ ${\ displaystyle (a + i) ^ {2} - (a + i-1) ^ {2} = 2a + 2i + 1}$ . Recunoașterea pătratelor poate fi realizată fie prin metode de aritmetică modulară (care elimină multe posibilități pentru pătrate: de exemplu, ultima cifră zecimală nu poate fi doar 2, 3, 7 sau 8) sau prin tabele speciale de pătrate.

Generalizări

În secolul al XX-lea au fost propuși diferiți algoritmi de factorizare care se bazau pe cei de la Fermat. Maurice Kraitchik a sugerat în anii 1920 că în loc să ia în considerare numerele întregi x și y astfel încât $n=x^{2}-y^{2}$ ${\ displaystyle n = x ^ {2} -y ^ {2}}$ ${\ displaystyle n = x ^ {2} -y ^ {2}}$ , am putea să le căutăm în așa fel încât n să împartă diferența dintre pătrate sau să căutăm soluții de congruență

x^{2}-y^{2}\equiv 0\mod n

{\ displaystyle x ^ {2} -y ^ {2} \ equiv 0 \ mod n}

{\ displaystyle x ^ {2} -y ^ {2} \ equiv 0 \ mod n}

sau echivalent

x^{2}\equiv y^{2}\mod n

{\ displaystyle x ^ {2} \ equiv y ^ {2} \ mod n}

{\ displaystyle x ^ {2} \ equiv y ^ {2} \ mod n}

În acest context, soluțiile „interesante” de congruență sunt cele în care x nu este nici congruent cu y, nici cu - y modulul n și în care atât x cât și y sunt coprimă cu n . Dacă n este impar și divizibil cu cel puțin două prime, s-a demonstrat că cel puțin jumătate din soluții sunt interesante. În acest caz | x - y | este strict între 1 și n și, prin urmare, este un factor non-trivial al lui n .

Atât algoritmul fracției continue, cât și site-ul pătratic se bazează pe această idee.

Bibliografie

Keith Devlin, Unde merge matematica . Bollati Boringhieri, Torino, 1994. ISBN 88-339-1182-9
Harold Davenport , Aritmetica superioară . Zanichelli, Bologna, 1994. ISBN 88-08-09154-6

linkuri externe

( EN ) Eric W. Weisstein, Metoda de factorizare a lui Fermat , în MathWorld , Wolfram Research.

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică