Algoritmos de factorización de enteros
algoritmo p + 1 de Williams es un algoritmo de factorización de enteros, uno de la familia de algoritmos de factorización de grupos algebraicos. Fue inventado por Hugh C. Williams en 1982.
Este funciona bien si el número N a ser factorizado contiene uno o más factores primos p tales que
- p + 1
es liso, i.e. p + 1 contiene únicamente factores pequeños. Este usa sucesiones de Lucas para realizar la exponenciación en un cuerpo cuadrático.
Es análogo al algoritmo p − 1 de Pollard.
Hugh Williams inventó el p método factorización 1 número entero en 1982 basado en John Pollard p método factorización -1 número entero; el p método 1 encuentra un factor de p cuando p es suave con respecto a una cota B . Hemos observado en un anterior ejercicio la estructura similar de de Pollard p -1 método y método de la curva elíptica de Lenstra, y Williams' p +1 acciones método la misma estructura de dos etapas; De Pollard p -1 método realiza multiplicaciones módulo p , método de curva elíptica de Lenstra realiza multiplicaciones sobre una curva elíptica, y Williams' p método 1 realiza multiplicaciones sobre un campo cuadrática utilizando secuencias de Lucas (similares a la cadena de Lucas en el Baillie-Wagstaff primality- las pruebas de ejercicio ). Una buena descripción de Williams' p método 1 se da en http://www.mersennewiki.org/index.php/P_Plus_1_Factorization_Method .
Williams' p método 1 utiliza el Lucas secuencia V 0 = 2, V 1 = A , V j = A · V j -1 - V j -2 , con todas las operaciones de módulo N , donde A es un número entero mayor que 2. la multiplicación por sucesivas potencias de primera se lleva a cabo como en el de Pollard p algoritmo -1; Cuando todos los productos a la cota B se acumulan, el máximo común divisor de N y el resultado V B - 2 puede ser un divisor de N si todos los factores de p 1 están a menos de B . Sin embargo, si A 2 - 4 es un no residuo cuadrático de p , el cálculo fallará, por lo que varios intentos deben realizarse con diferentes valores de A antes de concluir que p 1 no está B -smooth.
Dada la adición fórmula V m + n = V m V n - V m - n la duplicación de fórmula y V 2m = V m × V m - 2, la multiplicación se realiza por medio de una secuencia de Lucas que calcula dos valores a la vez. Comenzando con el par V kn y V ( k 1) n , y mirando a los bits en la representación binaria del multiplicador M , excluyendo el bit más significativo (que es siempre 1) y trabajando desde más significativo al menos significativo, calcular el par V 2KN , V (2 k 1) n cuando el bit es cero y el par V (2 k 1) n , V 2 ( k 1) n cuando el bit es uno.
La segunda etapa se encuentra factores que son B 1 -smooth a excepción de un solo factor primordial en el intervalo B 1 a B 2 . Se puede hacer de una manera similar a la segunda etapa de la de Pollard p método -1, pero un poco de álgebra nos da una mejor segunda etapa. Suponiendo que V n es el punto que sobrevive a la primera etapa, se multiplica el productos V k - V n para cada k divisible por 6 entre B 1 y B 2 , a continuación, tomar el máximo común divisor del producto con n para revelar el factor.
Su tarea consiste en escribir un programa que los factores de números enteros usando Williams p algoritmo 1. Cuando haya terminado, usted es bienvenido a leer o ejecutar una propuesta de solución, o para enviar su propia solución o discutir el ejercicio en los comentarios a continuación.
El algoritmo p − 1 de Pollard es un algoritmo de factorización de enteros en teoría de números, inventado por John Pollard en 1974. Es un algoritmo de propósito especial, lo que significa que es únicamente adecuado para enteros con factores de tipos específicos; es el ejemplo más simple de un algoritmo de factorización de grupos algebráicos.
Los factores que encuentra son aquellos para los que el número que precede el factor, p − 1, es potencia lisa; la observación esencial es que, trabajando en el grupo multiplicativo módulo un número compuesto N, también se trabaja en los grupos multiplicativos módulo todos los factores de N'. La existencia de este algoritmo permite también el concepto de primos fuertes, siendo primos para los cuales p − 1 tiene al menos un factor primo grande. Casi todos los números primos lo suficientemente grandes son fuertes; si un primo usado para propósitos criptográficos resultara ser no fuerte, es mucho más probable que fuera por malicia que a través de un error de generación de números aleatorios.
De Pollard
-Método
Definición 6 0,3 (potencia suave) Dejar que
sea un número entero positivo. Si
es un número entero positivo con la descomposición en factores primos , entonces es -poder suave ![$ N = \ prod p_i ^ {} $ e_i](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_tv_RMdUhLqqQ8uZ_Smo-3gM5NtHWj66RGvBzfGcpQ_yq9BQn1QB6ez6YP17LChUeqcA8S7v7g8njIjIfulG09XApeSnc6wn9e4QB5qgWNTZ2dSZVF6FkgFK_bHrRqaU-m1IrJ65imCCQYsjePHUi6tHutgqUaJJbsJGSm5sCmqdEgspwPCn6ZGdPI-r9Wr9TKgLPA87oGh=s0-d)
![$ $ N](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_sfgWBDnjF2Ou2XwHOG6-lJAAcR5UPbn8u66mGlErKm_M-hNJoQo2U_H1h0VVF-s0UqHSTc3MplLpNhiXGsmKxmvDOjUz45J8QRCr01eIy8PeYKfd7EFYF2f2ksoBcAJde2d-row1ClVbMl6yRpy2EvJ55MmnIy4_FMOJrKT7j3WkoQIVh-SSsQ467wOIwXl4kwLrTk=s0-d)
sipara todos . ![$ P_i ^ {e_i} \ leq B $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_tZbHUBmNN2wY8NIqTUufYhfvhiNfF4EDLmmorUR-IXbsMuTnl1M7crceSe3R7Sy6RtENriLoxhL0wZo_bs-rjPw3t_W2Gow1MnotlKjvw-AsJdu4OSccqypDeWC7dGgUGOq2oW86zOERefyV5vl5WNIlx0m0ji2TuMkIM1tBRPga16Pwr8Vmt87HIrYKtAj_yeqoarFf1Q=s0-d)
![$ I $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_uS0fEqzpCoCNjflHrrir3GqS18wi8xxUeIw26tEjWhwiaFpelGZ0Rb08l3IJC_FYRz4DPaVfS8dzRkaTrrNHmkjeRtIbr01M6yHhy66mmvqoM9yn2BGqEP-bnu3ci5DuIqUxp7GMfMJB9oF-Pba7M8ufFAmzyPeMoCIos7PtspF5z7OsVVhhxYln_lnmB34LgwhHph8aI=s0-d)
Por lo tanto es de potencia suave para , pero no está -POWER lisa (es -power liso). ![$ 30 = 2 \ cdot 3 \ cdot 5 $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_vsoi9GHqPAP66zDrE2_4ITGlKouyJ_sl-yjURhq0lzts-QBsPezgJXL6zQJgxJcJSs4wEa1zN6qHEas0Veq5DlL4pgUu1H1owgf1IrvnqnP_Q6yASMhg85KB4iP7ghk9RXXW2jHHCq77bGZK7sFVw5XQvvgedma0QCiBvHkrZ01kQLLCL8OrBSuNBKtUe368UCc0JvNcbhVg=s0-d)
![$ B $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_sKUEbK52ANwhUcbnjHrOleX-QKAr448Umt2qrDMSyl4EdFWUdvuEdXltJuRCp0W8GwzXuwHXo9rCFzy6GrdXjomfp3bZ1SFVMIqp3lRggAlE9E0_Q6DWVVOyu0TLpogYHtgUaWCUJfmdChvezQPgR3kbm_PBKJeR1jM_RfJOXmjL5it10QzbZt3UqPGXN4IUSXMvPMTJmu=s0-d)
![$ 150 = 2 \ cdot 3 \ cdot 5 ^ 2 $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_vUmDTk7rlEIJEpEsY0_q09QRRX674DMnGtn1Eze4iS997qamjpbmGf50gScnnxYOvWyoNbPDCTOcDd8UqDk8xKxqBJyx0Adx7tmk_ccsHpObFlcc8FVJiqxogIK79ClicqYNodjrvgOS-M-2DDNSCJpngJQ_1wYgLZg5ljvagDYVSnawCLdIQX8lxDRVnGdIpUwzjfi9zF=s0-d)
![$ 5 $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_sf1e2sacVFd4RN3bko5Pmt3IhyZOG2uxtTXoBdrmpAa2PSVf4Q91ZroLLMg0wPM08l7iR4A_WHz3ACsrMKYQ8My8OmlubazC8Aop-ws5-_UCir16xbZl3_x09UG3R_K3R8JfIMeOK0HiCjHV-ROdjyv19tU0vkIlEqHdD0N3KhYBEJRqego4Xv8GHcpZK6YnAMDWwDxkk=s0-d)
![$ B = 25 $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_uOt6a_IcUrc9LoQNVU_HKSLzJJB-QJeh3spFDSM3VAJx3uV4DoAQH9WolPmk3I48Ib4dFuaGUqZw5fXXX1uj0aosyjwfS8s5bm7BaDUEiqiC_d21RRBjvt9xV-yFNP6V8l6kJC6n_RSyvJGjQ0-Bv4AhMbE-UQXOtj9iqce6Lhxm6q15pDw1vx2vB2kOOE-7e9SA8SVSHF=s0-d)
Vamos a utilizar el siguiente algoritmo, tanto en el Pollard
Algoritmo 6 0.3 (mínimo común múltiplo de los primeros
números enteros) Dado un número entero positivo
, este algoritmo calcula el mínimo común múltiplo de los números enteros positivos de hasta
.
- [Sieve] usando, por ejemplo, la criba de Eratóstenes (algoritmo 1.2.3 ), calcular una lista
de todos los números primos
.
- [Multiplicar] Compute y la salida del producto .
Prueba . Let . Entonces ![$ M = \ lcm (1,2, \ ldots, B) $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_sFDpG6seFW5sEQouiv3KB14TvrDr3dmcd_IxWLtoCiv27Yuw9WH1fqbh9QBS8KkoKg3XFHdEojMu6h3ou8aA2r0RNdoHgiEnR31FwL9nlK_8zP3_9Xs39GQxZd_6AqNpLayRgVakgQDtYm3TbjxcXSCDDRUlrE9MQzfaGqvT6z3F7v3__cQQfhJAv7RSWG_u5iiI7AnrUDAg=s0-d)
donde
es el mayor poder de
que satisface
. Dado que , tenemos .
![$ R = \ lfloor \ log_p (B) \ rfloor $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_tP0waR5gyfxzOppYrup_KidvSauVr95HIem2wlELVjoeA-1RyH2FHAe2pC3r6y8Z1FSU8lYIj5t8IgOHNegfeSsIKqLrVC4uirLWWwUDOY_K_el7klq3aEklChTjF8ZYK0ogR_uq4-NgzNO6tJYtdxhk7q_Z3SI3ZK8SKp1g7KXxebZyWZxJ-Omtr1DMRsGX8GGSjzgJs-=s0-d)
![$ \ $ Qedsymbol](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_v9wzyRgrtEl-J0HawPldxpyBd2VxSIVQcEhQf7wosZh65jZFx8eUqtwV-BEHFLTNj5KMKddHzQscPsXRGb7ef8xuBQrSq1wGyMiMKXI55BPRU-qSHBfhS4y2mNURD3J8u92GhrGDHji6HF19WNOWB2ELnojC3E_uiddMGDs7L_2yNpAVLwjR6d2a8Mj5M2xAbpHTTQrg=s0-d)
donde
Dejar que
Deje , y observar que nuestra suposición de que es -poder suave implica que , por lo ![$ M = \ lcm (1,2,3, \ ldots, B) $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_tdwxTly0OFy4J6GyIFFi547flqx2COSZ_rVFlijjFcwatDrl2R1DZgJfcYh_ItqjPQcDkttrItgKzj5WkDUfogkrMdYhpkPQbKie0VE0vP0IEm4UDD4-kq6VFYmDXYJ6S-QbI3w3QheOrUOhhmTbPgDYLVKZ0zlYDkq4paaq9rpUNCo_OQhCgWoO4UWJJpPJdmEPhg6UMIOg=s0-d)
![$ P-1 $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_tc_o4h4s6R8pKKBXrsEFoKt9ArL5PHFaqHgoyKv9KwizMHx6aekDVTOZZnXYCabCN7GO61_Tcnmq61w0KpVfq3mQ-z5mrdRKOZcfZgH7kXwB69IunZPC0vPlT2D_qhZ3iR9WcyGpGLo7k7SZxaZqBK81zcnboJPDV-cCdz4vKwhHA_jk00qDEZulsFpPUm-J-AoSfday3I=s0-d)
![$ B $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_sKUEbK52ANwhUcbnjHrOleX-QKAr448Umt2qrDMSyl4EdFWUdvuEdXltJuRCp0W8GwzXuwHXo9rCFzy6GrdXjomfp3bZ1SFVMIqp3lRggAlE9E0_Q6DWVVOyu0TLpogYHtgUaWCUJfmdChvezQPgR3kbm_PBKJeR1jM_RfJOXmjL5it10QzbZt3UqPGXN4IUSXMvPMTJmu=s0-d)
![$ P-1 \ mediados m $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_v-gDoKninSN7kRj-ynpmwvUpNt_mPg8Imsuz6NUDtj5qWT5jIqct6q0fDQTU4BoX9S6gxQxhhLXxqtNrkaMtKLg8plL_Oxkr_9CG8NJPTwwaNyR3M6Fjt3EeizHK-03evIqZCg1nYRiH3aa4DvoIA0JPQ-EOAFHGZP3UW43lChN75ha1pITa4nV3be9lWoa5QWCDIGBeK9=s0-d)
Así
Si también entonces es un factor no trivial de . Si , a continuación, para cada divisor de potencia principal de . En este caso, repetir los pasos anteriores pero con una selección más pequeña de o, posiblemente, una elección diferente de . Además, es una buena idea para comprobar desde el principio si no es una potencia perfecta , y si es así sustituir por . Formalizamos el algoritmo de la siguiente manera:
![$ \ Gcd (a ^ m-1, N) $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_sHnd0UmnXi7zdW6XQXDRpDI54wnWDYF6G1rqw6V8gmAvjYSmw3JWV_YEC9KsQCDzloVLRvqVUlb7Nra94syI66BKMU0ayQoZHXcRKT3zQvl8wdv0LxaZm0ev9YzFd5yBPsmhTrzGxQ3ieW7Sxr7ahSgydEGFVcL-_Rn7JPpEmNbc53Xb32zcCPbHoESsk6btFYtGtq-Ga6=s0-d)
![$ A ^ m \ equiv 1 \ pmod {q ^ r} $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_thJRgAvoHLMMsA8g6Cl6sLh1mhWdQiyQF1sxENyLb5cYy0lZCq7UcHkbdOyuWIMbNWhvQs7_2A_Jf3ttWYHHASMEndFegC3lTGYerfmCUWfOO33PeafxldtTGrJGAugdVnR2eY6ypkaMAZgR8UtiIlldbCJmBpxUR6GLwU-RYR3UbkvqDWrylqixg8JoG5L908koEaXsUPjQ=s0-d)
![$ Q ^ r $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_vF5RuW4V2bqgtqSyVZRprkV5lTScgDlaKUq3ZvsEbNLoBVbjPSG3-BjUR-31lfFTTUxPWvAJqiFmXQdWzbdY-4VfiH3QOrW9DnfkxtTNnGSxYL74I19YXGl2jT6EIAjp9ocUm_0K-p3An2ZbpSTPhT99H2rSoBVkyNYRMsNjZXzn6v6o7l3IPy3RmiBgKVWvRuZL6aoLry=s0-d)
![$ N $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_v-nj_lvjw3PSevf0b8tmHIrlhCWmCGyLGr79UQa7HsWUm9CmbudroM8JF_mhaYw0Aienxe-eRJmP0auoLtvU4fv-GXgWoBakLN4dXpKpItexy41TcnuESrA-Qbru2PhX6VoJSiArYrsnI7E3oPZdJ5QjfbyoZDJ32WcTQQ6ZhB-EycqGl4gWv6A4g07YchFaQDK0lLfNc=s0-d)
![$ B $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_sKUEbK52ANwhUcbnjHrOleX-QKAr448Umt2qrDMSyl4EdFWUdvuEdXltJuRCp0W8GwzXuwHXo9rCFzy6GrdXjomfp3bZ1SFVMIqp3lRggAlE9E0_Q6DWVVOyu0TLpogYHtgUaWCUJfmdChvezQPgR3kbm_PBKJeR1jM_RfJOXmjL5it10QzbZt3UqPGXN4IUSXMvPMTJmu=s0-d)
![$ A $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_tV8CpCJqufi7JMEMpxCrMTQCw5FnOwcWvAtepugXnVMHaWQ6Ik9n6hVyt1VzD-mh-CiDzEkfhCv0Qlw_Fw2MKMJ7CTwPCMrtkz0k5KJBFTiNXPLB6dSabz84lgGfU4jmFDOiRaLKaAxA_mAxxfi3UHk53_aP0omwYzrIjzsTpnCe1sWbqHAFTTn2AxMizYog8umKxsy9k=s0-d)
![$ N $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_v-nj_lvjw3PSevf0b8tmHIrlhCWmCGyLGr79UQa7HsWUm9CmbudroM8JF_mhaYw0Aienxe-eRJmP0auoLtvU4fv-GXgWoBakLN4dXpKpItexy41TcnuESrA-Qbru2PhX6VoJSiArYrsnI7E3oPZdJ5QjfbyoZDJ32WcTQQ6ZhB-EycqGl4gWv6A4g07YchFaQDK0lLfNc=s0-d)
![$ M $ ^ r](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_tDMmkqcgG4LCAADL0JM_CTzgDu7JOZMif3G-xEbEAWDJPBZxG6cNpHiWRqfajn2dgw5J5zVKAdPKKULtHX2vmGupBrrGqTHSjJJD5SlrVnv3wGcU5lWu_ifmh4ePEH741Fzje_SKehdiwb2uWvB17wp_b1grgkvwHAAsPw6QYG57s9UWXSL1cxjoq4dtZZBaHrUKYcN3svQw=s0-d)
![$ N $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_v-nj_lvjw3PSevf0b8tmHIrlhCWmCGyLGr79UQa7HsWUm9CmbudroM8JF_mhaYw0Aienxe-eRJmP0auoLtvU4fv-GXgWoBakLN4dXpKpItexy41TcnuESrA-Qbru2PhX6VoJSiArYrsnI7E3oPZdJ5QjfbyoZDJ32WcTQQ6ZhB-EycqGl4gWv6A4g07YchFaQDK0lLfNc=s0-d)
![$ M $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_vGE_GSbnMIN4M3qRsaRwegpXJGypiFKjLp1n7BLxyiQ39XvEzITWqRA_NqJk4F9yfQ1ObetIpmrbjng1Kp-eqcDKda4-HSYDrV4VpkCyJHl7wEXnLunJG6rbQvbS-aqKhWjqLhRT5G8qrsXoAP4gIzMlrXnDN1fZgL6GqHklnlKHjQxrbxwoV7IGAiIxw8yWDbvd40dNq5hw=s0-d)
Algoritmo 6 0,3 (Pollard
Method) Dado un número entero positivo
y un salto
, este algoritmo intenta encontrar un factor no trivial
de
. (Cada primer
es probable que tenga la propiedad de que
es
-poder suave.)
Para fijo
Los siguientes ejemplos ilustran la Pollard
Ejemplo 6 0,3 En este ejemplo, Pollard funciona perfectamente. Let
. Tratamos de utilizar el Pollard
método con el
que dividir
. Tenemos ; teniendo tenemos![$ M = \ mcm (1,2,3,4,5) = 60 $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_swFTIwhy1Xphc4ZcHcOtW5y74JAXoboXYW61sEtMBOjaNRTTeZqF5XO5uheNohAeLqywnD-wUM9yM2x8c8AzzgDoet71PFmNmzO5dDoDA_QQlkiE50ijiLcPlpSWDl1tRnUk7qJBKOlq66c9vdMg_RVsrlVe7zxoJrSAyA-FkdJAFhL0oxIZbZ85StvUdCUm0n30RT3RlS-Q=s0-d)
![$ A = 2 $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_uSALXictD8K-Bx4vNuxHjggiwQ6VxV5TTB1UcsPdSdekSnFuGNvCWS39C7DNWLJpn1kfUG33fNiGB5vneMEf9LSxiduE2G1E_RABfXHm8PLES7w_bR_irGjDUg5dLUed_BDEdRm6M82csJeE45OXS99XWGlGaAZNZ1s5-wY8NcD2YOT6XpBp-lpa_uA0GkQMMW5nmZNJ-x=s0-d)
y
por lo que
es un factor de
.
y
por lo que
Ejemplo 6 0,3 En este ejemplo, se reemplaza
por entero mayor. Let
. Con
y
tenemos
y Con , que tiene![$ \ Mcd (2 ^ {60} -1,779167) = 1. $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_uYEOdAm3j5p1S3ajUalQf5JwRcvCinzoX_ws6sO3RgcIlFu1ywrJP4tsnDO3vM799fmpoLLePSuNzgVLuyFbU4fk7dW5v_3gQ349PwoxM4fCF_NMi8JHIFHQs6GjHuyIN5OSGM652P64GfZ-kSiHtA6mMGrg3BigX1mAPmnwsfYZBoAlp-2v2U1XIW4uFtwySA_1xduVRXLw=s0-d)
![$ B = 15 $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_ueq6DxtdqZrHthOEzEtQxgyL8xhfzE6i_RWK6SLS32YWUiC3rMUXp0f_YO5B660oUHqsCizfNkb9jV7EGVos0Pe33rBG6-DrpKu1zNcfgcdhk76xRKiiW6t6VxDIZiC6NrVpRHxYKIX16vmdkVfdQS2uK1Sv0gEH-bDEFVzpWEIC8pKoh_r-Gje2pIj6VQZxX8oISm9gG8DA=s0-d)
y
por lo que
es un factor no trivial de
.
y Con , que tiene
y
por lo que
Ejemplo 6 0,3 En este ejemplo, se reemplaza
por un número entero más pequeño. Let
. Supongamos
, por lo que , ![$ M = \ lcm (1,2, \ ldots, 7) = 420 $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_sYfZwmf59sg1V6AvHtgZ-HV7-YbrJT7Z1Cv_W75SCCFJ8DcG6ps56CluochpSIBpDRQVleQA_bo23yWp3lj6H0qh00dRHJ5BvqXS-oGVhdbIyNFmTP-VLF6RDwaX0jOritkDgR2CnBJ2GXpYxPjsQDQVEBX9oPXY7WO6Xds9vwGo08vSusjvz7FFh691vKHye-oRm5fnhomA=s0-d)
y , por lo que no obtienen un factor de . Si reemplazamos por el método de Pollard funciona:![$ \ Mcd (2 ^ {420} - 1, 4331) = 4331 $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_sc8hbRJapo4aoYI2ndazsccsM3ZNfIOkPOZEfayGHzzDPSwikMuTfQaJeDY8y-jHrlrVuxU77dvUVg68QDzLHXbNA-ZumAMoRFbcFx9q6T6RyAJoI-yT2sadQZvMb6jRO3-XNIzqSSIone5BqLIWD1K8CuykvuZeyWoJKPh3K0C7UHP7KgI_jxTgpaFgwluBVftQju2C8qGA=s0-d)
![$ 4331 $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_tcTSx69xNoqCW-L_8s8FRTorLBjjpSQJ7loxTTfdGvcpck6M8QtfaKPFj9aI3PpgdCCEyfgjLOCZADthIy8t3oedNR7AQWMR8aK-J2YoZT5_cjNab2CHNBOD2FvtR1YvX8-wf8KRXWNaPjY4XKpq6lzaB1kswkcJMrWH3mxDbB0ISBEKV4D4c1UyL1OhPNvZYHmaK7XjRFvA=s0-d)
![$ B $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_sKUEbK52ANwhUcbnjHrOleX-QKAr448Umt2qrDMSyl4EdFWUdvuEdXltJuRCp0W8GwzXuwHXo9rCFzy6GrdXjomfp3bZ1SFVMIqp3lRggAlE9E0_Q6DWVVOyu0TLpogYHtgUaWCUJfmdChvezQPgR3kbm_PBKJeR1jM_RfJOXmjL5it10QzbZt3UqPGXN4IUSXMvPMTJmu=s0-d)
![$ 5 $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_sf1e2sacVFd4RN3bko5Pmt3IhyZOG2uxtTXoBdrmpAa2PSVf4Q91ZroLLMg0wPM08l7iR4A_WHz3ACsrMKYQ8My8OmlubazC8Aop-ws5-_UCir16xbZl3_x09UG3R_K3R8JfIMeOK0HiCjHV-ROdjyv19tU0vkIlEqHdD0N3KhYBEJRqego4Xv8GHcpZK6YnAMDWwDxkk=s0-d)
y , por lo dividimos .![$ \ Mcd (2 ^ {60} -1,4331) = 61 $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_vgrdtRVMqsLFZhshMblaoHx3rijGm9CcxozBFcRhGu_j02mEJrlu3xTbPj597FlkyXM38G8J2-4J-NBi6tvsyJs8Hk-yh_GeX5abK3y5Oi6JrXu4aI1WuX9sZk58Q5ggmRXXgUj9xqNYz2TE7mzx75WyPoND-mdcGZYWSRJMZikaSnnoTtJHQI9F9ffWiwBeBJy3p-Km_lDg=s0-d)
![$ 4331 $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_tcTSx69xNoqCW-L_8s8FRTorLBjjpSQJ7loxTTfdGvcpck6M8QtfaKPFj9aI3PpgdCCEyfgjLOCZADthIy8t3oedNR7AQWMR8aK-J2YoZT5_cjNab2CHNBOD2FvtR1YvX8-wf8KRXWNaPjY4XKpq6lzaB1kswkcJMrWH3mxDbB0ISBEKV4D4c1UyL1OhPNvZYHmaK7XjRFvA=s0-d)
y , por lo que no obtienen un factor de . Si reemplazamos por el método de Pollard funciona:
y , por lo dividimos .
Ejemplo 6 0,3 En este ejemplo,
no funciona, pero
lo hace. Let
. Supongamos
, por lo que , ![$ M = \ lcm (1,2, \ ldots, 15) = 360360 $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_sr4oPhN1ONc-agPHARDOxxhG1utnTpTpWbXBphDr9fawNsNpHI24WwvjuXr1ykH-cA4f8ZWUC5gc3ovw_VSSCmshxw2emQFBqINUFCxWknOP37d_zpSMYv2SCQFZdM1irAuYrsUrUSLgr0zmWkWdxHgYI_6hTo0bGwmrnGenJkI_RP06u0NYDF8Q_cP5WrXTAMf17P6sxiiA=s0-d)
y , por lo que no obtienen un factor de . Si reemplazamos por , entonces el método de Pollard funciona:![$ \ Mcd (2 ^ {360360} - 1, 187) = 187 $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_stCoPZwizb3kS0s2v3K_4KP9F-ORYRylFKp8ZspcAxk0G_9MDSUJ5x3KIzHMvzmSTgIMkUypvgsj2i4ab8SCKvu6Z1eYzmv9cQvhPXXb_iZkNHT1zjAM15ovdhj0k6rUQKQxaBSqB8KNe23mdyu71St9KPqO4Zyz4PU9uKplXyi7xpu_AihNB6ySA_LlAnd51fGjegoWmn0w=s0-d)
![$ 187 $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_vK_rlQOjGDIo60_WKuP0i0fuUXwIbZ6O_6lw26YQw5l7DbX7k28KuINrNvXGz4PRrFLQtEqH-kHOi4H8OpKCwby2iWXpHE3A6HURQM6PauthfsSV7euPPcq1pmJu7I2u8gWPcNhM5Lo-kPmPQl_VoFT5o-j32dk99vd2tvXx-FpRZOKeHqOcJ4p6NH7mZx-vZbTP5vXj5nKw=s0-d)
![$ A = 2 $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_uSALXictD8K-Bx4vNuxHjggiwQ6VxV5TTB1UcsPdSdekSnFuGNvCWS39C7DNWLJpn1kfUG33fNiGB5vneMEf9LSxiduE2G1E_RABfXHm8PLES7w_bR_irGjDUg5dLUed_BDEdRm6M82csJeE45OXS99XWGlGaAZNZ1s5-wY8NcD2YOT6XpBp-lpa_uA0GkQMMW5nmZNJ-x=s0-d)
![$ A = 3 $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_uBnY5a39smARV_NXR15cXHJWadEQVUeW3xUo9O5CEkaPwL-FgcAq5VXMepaqKHerr1VOLJWmlrULsAgV9CyTNMHKFIr2Dwj59evo_4dzEUF1RlT0TuZZkCIZX2X5f08BfQ5vIdLDxvXyNDqUc9iya3L32zuyiRpYYvuUbj2L3VRS6WGlPek3VWMPkyIXjYeflWzZ4wfmE=s0-d)
y . Por lo tanto .
![$ 187 = 11 \ cdot 17 $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_tk3U0zg2Oled3_V2rFfIMrQFTXQhTJuvYK7nfxIyFBfzbAM39VafxznhZUBmjcJdqAv9e_kW1318Gm0ygsK2GiOpSXA7OMAbOsnt5JSdh7blbpqv-T9cUIvI3FKIy8MbyoshoVSvp-PPR4aTVPcbBi2lcdHbzdkM1ExbpEFMKhp_KwSPGLcH1s3wPEXFZW0DcOXhiwLOBcRQ=s0-d)
y , por lo que no obtienen un factor de . Si reemplazamos por , entonces el método de Pollard funciona:
y . Por lo tanto .
algoritmo rho de Pollard es un algoritmo especializado de factorización de números enteros. Fue inventado por John Pollard en 1975. Es especialmente efectivo a la hora de factorizar números compuestos que tengan factores pequeños.
Ideas principales
El algoritmo rho se basa en el algoritmo de la liebre y la tortuga y en la observación de que (como ocurre en el problema del cumpleaños) dos números x e y son congruentes módulo p con probabilidad 0,5 tras haberse elegido aleatoriamente números. Si p es factor de n, el número que se quiere factorizar, entonces , ya que p divide tanto a como a n.
El algoritmo rho emplea pues una función módulo n a modo de generador de una secuencia pseudoaleatoria. Hace funcionar una de las secuencias el doble de rápido que la otra, es decir, por cada iteración de una de las copias de la secuencia, la otra hace dos iteraciones. Sea x el estado actual de una secuencia e y el estado actual de la otra. En cada paso se toma el máximo común divisor (MCD) de |x − y| y n. Si este MCD llega a ser n, entonces finaliza el algoritmo con el resultado de fracaso, ya que esto significa que x = y y, por el algoritmo de la liebre y la tortuga, la secuencia ya ha completado su ciclo y seguir más allá sólo conseguiría repetir trabajo ya realizado.
El algoritmo
Entradas: n, el número que se desea factorizar; y f(x), una función pseudoaleatoria módulo n
Salidas: un factor no trivial de n, o bien un fracaso. (un factor trivial de n es n mismo o 1)
- x ← 2, y ← 2; d ← 1
- Mientras d = 1:
- x ← f(x)
- y ← f(f(y))
- d ← MCD(|x − y|, n)
- Si d = n, devuelve fracaso.
- De lo contrario, devuelve d.
Nótese que este algoritmo acabará en fracaso para todo n primo, pero también puede fallar para un n compuesto. En ese caso, se cambia la función f(x) y se intenta de nuevo.
Optimización
En 1980, Richard Brent publicó una versión del algoritmo más rápida. Empleó las mismas ideas fundamentales que Pollard pero un método distinto de detección de ciclos, reemplazando el algoritmo de la liebre y la tortuga por el algoritmo de Brent para la detección de ciclos.
Pollard y Brent introdujeron una mejora adicional. Observaron que si , entonces también se cumple que para cada entero positivo . En particular, en lugar de computar en cada paso, basta definir como el producto de cien términos consecutivos de módulo n, para luego computar un solo . Se obtiene un importante ahorro de tiempo, ya que se ven reemplazados 100 cálculos de un máximo común divisor por 99 multiplicaciones módulo y un solo . A veces se da lugar a un error en el algoritmo al introducir un factor repetido, por ejemplo, cuando es un cuadrado. Sin embargo, basta con volver atrás al cálculo anterior del , donde , y a partir de ahí volver a usar el algoritmo rho original.
En la práctica
El algoritmo es muy rápido en la factorización de números que tienen factores pequeños. Por ejemplo, en un equipo de trabajo de 3 GHz, el algoritmo original halló el factor 274177 del sexto número de Fermat (18446744073709551617) en 26 milisegundos. Por contra, la variante de Richard Brent halló el mismo factor en sólo 5 milisegundos. Sin embargo, en el caso de un semiprimo del mismo número de cifras (10023859281455311421), el mismo equipo tardó 109 milisegundos en encontrar un factor con el algoritmo original, y 31 con la variante de Richard Brent.
Para f se elige un polinomio con coeficientes enteros. Los más comunes son de la forma
El éxito más relevante del algoritmo rho ha sido la factorización del octavo número de Fermat, realizada por Pollard y Brent. Emplearon la variante de Brent, que halló un factor hasta entonces desconocido. La factorización completa de F8 tardó dos horas en un UNIVAC 1100/42.
Ejemplo
Sea n = 8051 y f(x) = x2 + 1 mód 8051.
i | xi | yi | MCD(|xi − yi|, 8051) |
---|---|---|---|
1 | 5 | 26 | 1 |
2 | 26 | 7474 | 1 |
3 | 677 | 871 | 97 |
97 es un factor no trivial de 8051. Otros valores de c pueden dar lugar al cofactor (83) en lugar de 97.
Complejidad
El algoritmo ofrece un equilibrio entre su tiempo de ejecución y la probabilidad de encontrar un factor.
Si n es producto de dos primos distintos de tamaño similar, al ejecutar el algoritmo en O(n1/4 polylog(n)) iteraciones se obtiene un factor con probabilidad aproximadamente 0,5. (Nótese que ésta es una afirmación heurística, y que sigue abierto un análisis riguroso del algoritmo.)
No hay comentarios:
Publicar un comentario