Metoda de factorizare a lui Euler

Metoda factorizarea Euler este un algoritm conceput de Euler a factorului naturale numere în numere prime .

Se bazează pe reprezentarea numărului n (de luat în calcul) ca suma a două pătrate în două moduri distincte și, din acest motiv, nu se aplică nici numerelor sub forma 4 k +3, nici celor în care un număr prim al acestei forme este prezent la un exponent impar în factorizarea lui n . Acest lucru reduce foarte mult câmpul său de aplicabilitate, deoarece chiar și multe semi-prime în forma 4 k +1 sunt produsul a două prime de tipul 4 k +3.

Din acest motiv nu este adesea folosit ca metodă de factorizare, deoarece nu este posibil să se știe a priori dacă un număr dat poate fi sau nu luat în calcul cu acest algoritm.

Algoritm

Având o scriere dublă a lui n ca suma a două pătrate:

n=a^{2}+b^{2}=c^{2}+d^{2}

{\ displaystyle n = a ^ {2} + b ^ {2} = c ^ {2} + d ^ {2}}

{\ displaystyle n = a ^ {2} + b ^ {2} = c ^ {2} + d ^ {2}}

( a , b , c și d pot fi găsite, de exemplu, cu tabele de pătrate) și presupunând că b și d au aceeași paritate (adică sunt ambele pare sau ambele impare) și că a este mai mare decât c (și în consecință d mai mare decât b ) avem

a^{2}-c^{2}=(a-c)(a+c)=(d-b)(d+b)=d^{2}-b^{2}

{\ displaystyle a ^ {2} -c ^ {2} = (ac) (a + c) = (db) (d + b) = d ^ {2} -b ^ {2}}

{\ displaystyle a ^ {2} -c ^ {2} = (a-c) (a + c) = (d-b) (d + b) = d ^ {2} -b ^ {2}}

( a - c ) și ( d - b ) sunt ambele pare și, prin urmare, au un divizor comun non-banal k (care poate fi găsit rapid cu utilizarea algoritmului euclidian ); plasarea

a-c=kA,~~~d-b=kB

{\ displaystyle ac = kA, ~~~ db = kB}

{\ displaystyle a-c = kA, ~~~ d-b = kB}

se pare că A și B sunt coprimi . Prin substituire avem

kA(a+c)=kB(d+b)

{\ displaystyle kA (a + c) = kB (d + b)}

{\ displaystyle kA (a + c) = kB (d + b)}

și, prin urmare, prin lema lui Euclid , A împarte d + b și B împarte a + c și, în special, dacă $a+c=BC$ ${\ displaystyle a + c = BC}$ ${\ displaystyle a + c = BC}$ ,