b'\n_START_ARTICLE_\nFactoritzaci\xc3\xb3 per prova de divisions\n_START_PARAGRAPH_\nEn matem\xc3\xa0tiques i m\xc3\xa9s concretament en teoria de nombres la Factoritzaci\xc3\xb3 per prova de divisions \xc3\xa9s un algorisme que troba un divisor no trivial d\'un enter positiu si \xc3\xa9s que n\'existeix cap. _NEWLINE_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._NEWLINE_Si en troba algun llavors el nombre en q\xc3\xbcesti\xc3\xb3 \xc3\xa9s un nombre compost altrament \xc3\xa9s un nombre primer. Per tant l\'algorisme de prova de divisions \xc3\xa9s tant un algorisme de factoritzaci\xc3\xb3 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\xc3\xa9s amb el quocient, llavors s\'arriba a la descomposici\xc3\xb3 del nombre en factors primers. _NEWLINE_Per regla general s\'utilitza aquest procediment nom\xc3\xa9s per trobar factors fins a un cert l\xc3\xadmit, llavors es parla de prova de divisions incompleta.\n_START_SECTION_\nDescripci\xc3\xb3 de l\'algorisme\n_START_PARAGRAPH_\nSigui un enter compost donat n (en aquest article, n representa \xc2\xabl\'enter a factoritzar\xc2\xbb), les proves de divisions consisteixen a intentar dividir n per cada nombre primer inferior o igual a ._NEWLINE_\xc3\x89s segur que si l\'algorisme acaba sense detectar cap divisor, el nombre \xc3\xa9s primer perqu\xc3\xa8 si fos compost com que no t\xc3\xa9 cap divisor que sigui un nombre primer i que sigui m\xc3\xa9s petit que  hi hauria dos nombres m\xc3\xa9s grans que  que multiplicats donarien n per\xc3\xb2 aix\xc3\xb2 \xc3\xa9s una contradicci\xc3\xb3._NEWLINE_Si P(i) \xc3\xa9s l\'i-\xc3\xa8sim nombre primer i n el nombre del que es vol trobar un factor l\'algorisme seria com segueix:_NEWLINE_Trobar un factor de (n)_NEWLINE_i=0_NEWLINE_imax=_NEWLINE_Fer mentre residu<>0 .i. i<imax_NEWLINE_i=i+1_NEWLINE_Residu=n\\P(i)_NEWLINE_Fi fer_NEWLINE_Si i>imax llavors _NEWLINE_retorna Prova de primalitat=Cert_NEWLINE_retorna factor = n_NEWLINE_altrament_NEWLINE_retorna Prova de primalitat=Fals_NEWLINE_retorna factor = P(i)_NEWLINE_Fisi_NEWLINE_Si el que es vol \xc3\xa9s 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:_NEWLINE_Descompondre n en factors primers. _NEWLINE_m=n_NEWLINE_Prova de primalitat =fals_NEWLINE_Descomposici\xc3\xb3 en factors primers$=""_NEWLINE_Fer mentre Prova de primalitat = Fals_NEWLINE_Trobar un factor de (m)_NEWLINE_Descomposici\xc3\xb3 en factors primers$ = Descomposici\xc3\xb3 en factots primers$ + "\xc2\xb7" + "factor"_NEWLINE_m=m/factor_NEWLINE_Fifer_NEWLINE_Retorna "n = "+Descomposici\xc3\xb3 en factors primers$\n_START_SECTION_\nExemple\n_START_PARAGRAPH_\nPer factoritzar el nombre 1746._NEWLINE_En provar 2 resulta que \xc3\xa9s divisible._NEWLINE_Es divideix 1746 entre 2 i d\xc3\xb3na 873._NEWLINE_Ara es prova de dividir entre 2 i no \xc3\xa9s possible, per tant es passa el seg\xc3\xbcent nombre primer, el 3, 873 \xc3\xa9s divisible entre 3._NEWLINE_Es divideix entre 3 i d\xc3\xb3na 291_NEWLINE_Aquest nombre es pot tornar a dividir entre 3 i d\xc3\xb3na 97. Ara es prova de dividir el 97 entre 3,5 i 7 i resulta que no \xc3\xa9s divisible entra cap d\'ells. No cal provar de dividir-lo entre 11 perqu\xc3\xa8 11 \xc3\xa9s m\xc3\xa9s gran de . Per tant la descomposici\xc3\xb3 en factors primers de 1746 \xc3\xa9s:_NEWLINE_1746=2\xc2\xb73\xc2\xb2\xc2\xb797\n_START_SECTION_\nDetalls d\'implementaci\xc3\xb3\n_START_PARAGRAPH_\nSi es vol implementar l\'algorisme cal emmagatzemar els nombres primers en mem\xc3\xb2ria, una manera de fer-ho estalviant espai a canvi d\'un petit augment de temps de c\xc3\xa0lcul, consisteix a emmagatzemar nom\xc3\xa9s la difer\xc3\xa8ncia entre cada nombre i l\'anterior. Llavors es van reconstruint els nombres primers sumant les difer\xc3\xa8ncies. D\'aquesta manera nom\xc3\xa9s cal un byte per cada nombre fins al 1.872.851.947 perqu\xc3\xa8 en cap cas la difer\xc3\xa8ncia \xc3\xa9s m\xc3\xa9s gran de 256. _NEWLINE_En el cas de la variant en qu\xc3\xa8 es proven nom\xc3\xa9s nombres que s\xc3\xb3n congruents a 1 o 5 m\xc3\xb2dul 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\xc3\xb2dul 30 les s\xc3\xa8rie de quantitats a sumar sucessivament ha de ser: 6,4,2,4,2,4,6,2 i es torna a comen\xc3\xa7ar pel 6,4,2..._NEWLINE_Si el que es busca \xc3\xa9s descompondre el nombre en factors primers cada cop que es crida la rutina de buscar un factor no cal tornar a comen\xc3\xa7ar pel 2, n\'hi ha prou amb repetir l\'\xc3\xbaltim factor provat i continuar amb els seg\xc3\xbcents. Tamb\xc3\xa9 es pot fer que la rutina de buscar el factor retorni tamb\xc3\xa9 el quocient i estalviar de repetir la divisi\xc3\xb3 en la rutina externa._NEWLINE_Per saber si un nombre \xc3\xa9s divisible entre els nombres m\xc3\xa9s petits no sempre cal fer la divisi\xc3\xb3, es pot aprofitar la informaci\xc3\xb3 que d\xc3\xb3na el fet de tenir escrit el nombre en una base determinada per saber-ho amb un esfor\xc3\xa7 computacional molt m\xc3\xa9s petit que el que cal per fer la divisi\xc3\xb3. Per exemple en base 10 els nombres parells s\xc3\xb3n els que tenen l\'\xc3\xbaltima xifra parell, en base dos els nombres parells s\xc3\xb3n 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.\n_START_SECTION_\nComplexitat\n_START_PARAGRAPH_\nLa prova de divisions necessita en el pitjor cas de l\'ordre de  divisions, donat que la quantitat de nombres primers m\xc3\xa9s petis d\'un nombre donat tendeix asint\xc3\xb2ticament a la meitat del logaritme neperi\xc3\xa0 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 \xc3\xa9s , on la constant c dep\xc3\xa8n del procediment._NEWLINE_La durada mitjana \xc3\xa9s del mateix tipus que en el pitjor cas.\n_START_SECTION_\n\xc3\x80mbit d\'aplicaci\xc3\xb3\n_START_PARAGRAPH_\nLa factoritzaci\xc3\xb3 per assaig de divisions incompleta sovint es fa servir per obtenir una visi\xc3\xb3 general de la factoritzaci\xc3\xb3 d\'un nombre. Si no resulta possible amb un nombre d\'assajos raonable llavors es passa a fer servir algorismes de factoritzaci\xc3\xb3 m\xc3\xa9s complexos._NEWLINE_A m\xc3\xa9s, sovint la factoritzaci\xc3\xb3 per assaig de divisions \xc3\xa9s un pas parcial necessari per algorismes m\xc3\xa9s complexos._NEWLINE_No obstant aix\xc3\xb2, per a n amb almenys un factor petit, les proves de divisions poden ser una manera r\xc3\xa0pida de trobar aquest factor petit. Per a un n aleatori, existeix un 50% d\'oportunitats de qu\xc3\xa8 2 sigui un factor de n, i 33% d\'oportunitats de qu\xc3\xa8 3 sigui un factor, i aix\xc3\xad 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._NEWLINE_Per aplicacions de criptografia no \xc3\xa9s aplicable aquest m\xc3\xa8tode per factoritzar nombres perqu\xc3\xa8 el nombres compostos que es fan servir ja es trien de manera que els seus factors siguin grans.'