Método d'factorización de Fermat

Pierre de Fermat

El método d'factorización de Fermat es basa en la representació d'un número real o un número complejo com la diferència de dos quadrats:

$n=a^2-b^2$

Eixa diferència es pot factorizar algebraicamente com $(a+b)(a-b)$; si cap d'eixos factors és igual a 1, es tracta d'una factorización pròpia de $n$.

Tot número impar es pot representar d'esta manera. En efecte, si $n=cd$ és una factorización de $n$, llavors:

$n={\left(\frac{c+d}{2}\right)}^2-{\left(\frac{c-d}{2}\right)}^2$

Com $n$ és impar, $c$ i $d$ també són impars, per lo que el seu semisuma i semidiferencia són abdós sancers. (Un múltiple de quatre també és una diferència de quadrats: en eixe cas es poden plantejar $c$ i $d$com a número par.)

En la seua forma més simple, el método de Fermat pot ser inclús més llent que el de divisió per tentativa en el pijor dels casos. No obstant, la combinació de divisió per tentativa i el método de Fermat és més efectiu que l'us exclusiu d'un d'ells.

Método bàsic

Es van prenent varis valors de $a$, en l'esperança de que $a^2-n=b^2$ siga un quadrat.

Si $n$ té més de dos factors primers, este procediment primer troba la factorización en el menor valor de $a$ i $b$. És dir, $a+b$ és el menor factor major o igual que la raïl quadrada de $n$. Per tant, $a-b=\frac{n}{a+b}$ és el major factor menor o igual que $\sqrt{n}$. Si el procediment torna $n=1\cdot n$, llavors $n$ deu ser primer.

Per a $n=cd$, siga $c$ el major factor menor que la raïl. $a=\frac{c+d}{2}$, per tant, el número de passos requerits és aproximadament:

$\frac{c+d}{2}-\sqrt{n}=\frac{{(\sqrt{d}-\sqrt{c})}^2}{2}=\frac{(\sqrt{n}-c{)}^2}{2c}$.

Si $n$ és primer (és dir, $c=1$), ¡fan falta $O(n)$ passos!. Esta és des de després una mala forma de demostrar la primalidad d'un número. Pero si $n$ té un factor pròxim a la seua raïl quadrada, el método funciona ràpidament. Concretament, si $c$ diferix de $\sqrt{n}$ en menys de ${\left(4n\right)}^{1/4}$, llavors el método solament necessita un pas, i açò és independent del tamany de $n$.

Eixemple

Prenga's el número $n=5959$ per a realisar la seua factorización, es procedix aixina:

A:	78	79	80
Bcuad:	125	282	441

El tercer intent produïx un quadrat. $A=80$, $B=21$, i els factors són $A-B=59$ i $A+B=101$.

Factorización de Fermat i divisió per tentativa

Intentem factorizar l'número primo $n=2345678917$, pero també calcular i $a-b$. Escomençant per $\sqrt{n}$ i pujant des d'ahí, queden aixina tabulados les senyes:

A:	48433	48434	48435	48436
Bcuad:	76572	173439	270308	367179
B:	276,7	416,5	519,9	605,9
A-B:	48156,3	48017,5	47915,1	47830,1

En la pràctica, es pot ignorar l'última fila fins que $b$ siga un número entero. Pero cal observar que si $n$ tinguera un factor menor que la seua raïl pero major que $A-B=47830,1$, el método de Fermat ya ho hauria trobat.

La divisió per tentativa normalment tindria que seguir fins al major cosí menor que $48432$; pero despuix de sol quatre passos en el método de Fermat, basta intentar-ho fins a $47830$ per a trobar un factor o determinar la primalidad.

Açò sugerix l'implementació d'un método que combine els ya descrits. Basta prendre una cota $c>\sqrt{n}$ i usar Fermat per als factors compresos entre $\sqrt{n}$ i $c$. Açò deixa una cota per a la divisió per tentativa de $c-\sqrt{c^2-n}$. En l'eixemple anterior, en $c=48436$ la cota per a la divisió per tentativa és $47830$. Una atra opció raonable seria $c=55000$, que deixa una cota de $28937$.

Seguint en el método de Fermat, s'obté un rendiment cada volta menor. Aixina, normalment un pararia abans d'aplegar a este punt:

A:	60001	60002
Bcuad:	1254441084	1254561087
B:	35418,1	35419,8
A-B:	24582,9	24582,2

Vore també

• Factorización de sancers