Factorització per prova de divisions

En matemàtiques i més concretament en teoria de nombres la Factorització per prova de divisions és un algorisme que troba un divisor no trivial d'un enter positiu si és que n'existeix cap.

La idea consisteix a provar de dividir el nombre entre tots els divisors possibles fins a trobar-ne un que doni residu zero o veure que no n'hi ha cap.

Si en troba algun llavors el nombre en qüestió és un nombre compost; altrament, és un nombre primer. Per tant l'algorisme de prova de divisions és tant un algorisme de factorització dels enters com una prova de primalitat. Si un cop trobat un divisor, es divideix el nombre entre el divisor i es repeteix el procés amb el quocient, llavors s'arriba a la descomposició del nombre en factors primers.

Per regla general s'utilitza aquest procediment només per trobar factors fins a un cert límit, llavors es parla de prova de divisions incompleta.

Descripció de l'algorisme

Sigui un enter compost donat n (en aquest article, n representa «l'enter a factoritzar»), les proves de divisions consisteixen a intentar dividir n per cada nombre primer inferior o igual a ${\sqrt {n}}$.

És segur que si l'algorisme acaba sense detectar cap divisor, el nombre és primer perquè si fos compost com que no té cap divisor que sigui un nombre primer i que sigui més petit que ${\sqrt {n}}$ hi hauria dos nombres més grans que ${\sqrt {n}}$ que multiplicats donarien n però això és una contradicció.

Si P(i) és l'i-èsim nombre primer i n el nombre del que es vol trobar un factor l'algorisme seria com segueix:

Trobar un factor de (n)
i=0
imax=${\sqrt {n}}$
Fer mentre residu<>0 .i. i<imax
i=i+1
Residu=n\P(i)
Fi fer
Si i>imax llavors 
retorna Prova de primalitat=Cert
retorna factor = n
altrament
retorna Prova de primalitat=Fals
retorna factor = P(i)
Fisi

Si el que es vol és descompondre n en factors primers un cop trobat un factor es divideix n entre el factor i es repeteix l'algorisme fins a arribar a un nombre primer:

Descompondre n en factors primers.
m=n
Prova de primalitat =fals
Descomposició en factors primers$=""
Fer mentre Prova de primalitat = Fals
Trobar un factor de (m)
Descomposició en factors primers$ = Descomposició en factots primers$ + "·" + "factor"
m=m/factor
Fifer
Retorna "n = "+Descomposició en factors primers$

Exemple

Per factoritzar el nombre 1746. En provar 2 resulta que és divisible. Es divideix 1746 entre 2 i dona 873. Ara es prova de dividir entre 2 i no és possible, per tant es passa el següent nombre primer, el 3, 873 és divisible entre 3. Es divideix entre 3 i dona 291 Aquest nombre es pot tornar a dividir entre 3 i dona 97. Ara es prova de dividir el 97 entre 3,5 i 7 i resulta que no és divisible entra cap d'ells. No cal provar de dividir-lo entre 11 perquè 11 és més gran de ${\sqrt {97}}=9,84$. Per tant la descomposició en factors primers de 1746 és:

1746=2·3²·97

Variants

Per implementar l'algorisme descrit cal la llista dels nombres primers més petits que l'arrel quadrada del nombre que es vol factoritzar, aquesta llista es pot aconseguir, per exemple amb el garbell d'Eratòstenes. Algunes variants de l'algorisme treballen sense haver de construir prèviament aquesta llista. Una possibilitat és no realitzar la prova de divisió només amb els nombres primers sinó amb tots els nombres (excepte l'1). El resultat és el mateix, però es realitzen divisions supèrflues. Algunes d'aquestes divisions supèrflues es poden evitar, per exemple un cop provat el 2 llavors provar només els nombres senars. D'aquesta forma el nombre de divisions a fer es redueix a:

${{\sqrt {n}} \over 2}$

Aquesta idea es pot generalitzar encara més, els nombres senars són els nombres congruents a 1 mòdul 2 (veure aritmètica modular i congruència sobre els enters). Els nombres que no són múltiples de 2 ni 3 són els que són congruents a 1 o 5 mòdul 6, o els que no són múltiples ni de 2 ni de 3 ni de 5 són els que són congruents a 1,7,11,13,17,19,23 o 29 mòdul 30. En el primer cas el nombre de divisions a fer és de:

${{\sqrt {n}} \over 3}$

I en el segon es redueix una mica més a:

${4{\sqrt {n}} \over 15}$

Detalls d'implementació

Si es vol implementar l'algorisme cal emmagatzemar els nombres primers en memòria, una manera de fer-ho estalviant espai a canvi d'un petit augment de temps de càlcul, consisteix a emmagatzemar només la diferència entre cada nombre i l'anterior. Llavors es van reconstruint els nombres primers sumant les diferències. D'aquesta manera només cal un byte per cada nombre fins al 1.872.851.947 perquè en cap cas la diferència és més gran de 256.

En el cas de la variant en què es proven només nombres que són congruents a 1 o 5 mòdul 6 es poden resseguir eficientment aquests nombres a base de sumar alternativament 2 o 4 al nombre anterior. En el cas de la variant dels congruents mòdul 30 les sèrie de quantitats a sumar sucessivament ha de ser: 6,4,2,4,2,4,6,2 i es torna a començar pel 6,4,2...

Si el que es busca és descompondre el nombre en factors primers cada cop que es crida la rutina de buscar un factor no cal tornar a començar pel 2, n'hi ha prou amb repetir l'últim factor provat i continuar amb els següents. També es pot fer que la rutina de buscar el factor retorni també el quocient i estalviar de repetir la divisió en la rutina externa.

Per saber si un nombre és divisible entre els nombres més petits no sempre cal fer la divisió, es pot aprofitar la informació que dona el fet de tenir escrit el nombre en una base determinada per saber-ho amb un esforç computacional molt més petit que el que cal per fer la divisió. Per exemple en base 10 els nombres parells són els que tenen l'última xifra parell, en base dos els nombres parells són els que acaben en 0. Vegeu l'article criteris de divisibilitat pels criteris en base 10 i l'article sobre les cintes de Pascal per veure la forma de deduir els criteris de divisibilitat de qualsevol nombre en qualsevol base.

Complexitat

La prova de divisions necessita en el pitjor cas de l'ordre de ${\frac {2{\sqrt {n}}}{\ln n}}$ divisions, donat que la quantitat de nombres primers més petis d'un nombre donat tendeix asintòticament a la meitat del logaritme neperià del nombre. En les variants que es conformen a treballar sense una llista de nombres primers el nombre de les divisions en el pitjor cas és $c{\sqrt {n}}$, on la constant c depèn del procediment.

La durada mitjana és del mateix tipus que en el pitjor cas.

Àmbit d'aplicació

La factorització per assaig de divisions incompleta sovint es fa servir per obtenir una visió general de la factorització d'un nombre. Si no resulta possible amb un nombre d'assajos raonable llavors es passa a fer servir algorismes de factorització més complexos.

A més, sovint la factorització per assaig de divisions és un pas parcial necessari per algorismes més complexos.

No obstant això, per a n amb almenys un factor petit, les proves de divisions poden ser una manera ràpida de trobar aquest factor petit. Per a un n aleatori, existeix un 50% d'oportunitats de què 2 sigui un factor de n, i 33% d'oportunitats de què 3 sigui un factor, i així successivament. Es pot demostrar que un 88% de tots els enters positius tenen un factor inferior a 100, i que un 91% tenen un factor inferior a 1000.

Per aplicacions de criptografia no és aplicable aquest mètode per factoritzar nombres perquè el nombres compostos que es fan servir ja es trien de manera que els seus factors siguin grans.

Enllaços externs

• Javascript Prime Factor Calculator using trial division. Can handle numbers up to about 9×10¹⁵