Título: Test de primalidad Miller-Rabin con GMP Publicado por: soplo en 29 Octubre 2010, 22:16 pm Hola.
Estoy teniendo muchos problemas con la dichosa rutinita esta y aún no funciona. Para saberlo le meto un número que sé que es primo (porque aparece en alguna lista de números primos en internet) y me dice que no es primo así que no está bien. Os pongo lo que tengo hecho a ver si encontramos la causa: Puede salir un tocho porque voy a poner muchas anotaciones para que no os perdais con GMP pero bueno ... Aquí empiezo. Incluyo gmp para poder trabajar con números grandes, defino dos funciones y creo una variable 104729 que es un número primo conocido para pasar el test. El resultado debe ser que ese número es primo. Miller Rabin tiene un factor de error de 1/4 así que siempre se debe repetir el test varias veces para asegurarse que siempre que ese número pasa el test se devuelve que es primo. Si una sola vez saliera que es compuesto ya sabríamos que el númeor es compuesto. Código: # include <gmp.h> Ahora el test de Miller Rabin en sí mismo. Para facilitar la rapidez lo primero que hago es ver si es divisible por los primeros diez mil números primos conocidos. Si es divisible por alguno es que el número es compuesto y no hay que perder mas tiempo. Código: int miller_rabin ( mpz_t Num, int Comprobaciones ) Omito la función ComprobarDivisibilidad para no hacer mas tocho y me centro en Miller Rabin. Miller Rabin requiere que se encuentre un par de números R y S tal que satisfagan que (N-1)=R * 2^S. Además R debe ser impar. Num es el número a comprobar. NumDec es Num-1 Código: mpz_init(d); Inicializo valores aleatorios (la semilla) Código: gmp_randstate_t semilla; Inicializo algunos valores que necesito Código: mpz_init(ValorAleat); Aquí comienza el bucle de comprobación. Como dije MillerRabin tiene un factor de error y para asegurarnos que la respuesta es correcta en vez de hacer el test una vez lo hacemos varias. En mi caso 10 porque llamé a la función MillerRabin con el parámetro Comprobaciones=10. Lo de EsPrimo es un valor boleano. Si antes resultó que es divisible entre algún número primo que no haga el bucle y se vaya al final. Código: while ( Comprobaciones-- > 0 && EsPrimo) { Código: mpz_clear(ValorAux); Pues no me funciona y no veo la razón. Se que estoy muy cerca pero hay algo que se me escapa. Ese código se puede optimizar mucho. Lo he puesto así porque se ven mas claros los pasos que doy para seguir a MillerRabin. Título: Re: Test de primalidad Miller-Rabin con GMP Publicado por: APOKLIPTICO en 29 Octubre 2010, 22:43 pm Wii! Copado, genial, realmente muy bien, como siempre, un par de críticas constructivas, si me permitis...
1) Comprobar la divisibilidad con los primeros 10.000 primos, te va a tomar bastante tiempo, que realmente no es necesario si utilizas miller rabin. Las comprobaciones que deberías hacer para eliminar rápidamente números compuestos triviales son: Si es par (num%2 == 0) y si es "2" o menor a "2" (1, 0 o negativos). Si es par, la respuesta seria obviamente que no es primo, la comprobación de paridad se debe hacer despues de comprobar si es igual a "2" ya que "2" es par y primo (el unico caso). "0" y "1" son valores inválidos o no primos (ya que las condiciones necesarias para que un número sea primo es que sea divisible por 1 y por si mismo, en caso de "1" si mismo es igual a "1" asi que no tiene sentido y "0" no es divisible por si mismo). Si es "2" entonces es primo. Probar con los primeros 10000 primos, va a disminuir mucho tu cálculo de primos por segundo. 2) Quizas convendría que el número aleatorio, no sea mayor a 1000 o a 500, para disminuir tiempo de cálculo. Total, solo necesitas a lo sumo 10 números. 3) No entendí muy bien algunas partes del código, las tendría que ver con mayor detenimiento, pero quiero ver si entendiste bien el algoritmo, porque me suena que hay algo que no está bien: a) Si a^d mod n != 1 y != -1 (esto significa n -1). Entonces n es probablemente primo. b) Hay que probar todos los a^(d^(2*s)) mod n. Siendo "s" la variable que va desde 1 hasta las veces que lo dividiste. Vas incrementando "s" hasta que de -1 o hasta que llegues a las veces que lo dividiste. Si te dio -1 alguna de las potencias, es probablemente primo, sino, es compuesto. PD: La próxima utilizá los tags [code=cpp Título: Re: Test de primalidad Miller-Rabin con GMP Publicado por: soplo en 29 Octubre 2010, 23:18 pm a mi también me parece que al final he acabado mareando la perdiz y poniendo algo mal. Por eso no me da bien. Tengo en mente hacer un manual de operaciones GPM porque es bastante antipático tal como viene en el manual de gnu mp 5.1.
En cualquier caso si tienes alguna duda con alguna línea no dudes en decirlo a ver si encontramos donde está el error (que seguro que es de bulto porque ya no se cuantas veces lo he tocado) je je je Título: Re: Test de primalidad Miller-Rabin con GMP Publicado por: APOKLIPTICO en 29 Octubre 2010, 23:22 pm Estoy luchando con gmp para instalarlo bajo mingw, pero me sigue tirando undefined references...
Ahora cuando lo haga andar, me parece que ya se donde está el problema, en un lugar pones que si valoraux == 0 es compuesto, en realidad, si valoraux = -1 entonces es primo... Se tienen que probar todos los "s" para que sea compuesto. Título: Re: Test de primalidad Miller-Rabin con GMP Publicado por: WestOn en 30 Octubre 2010, 00:34 am Muy bueno, al final te salió bien ;) me alegro
Saludos Título: Re: Test de primalidad Miller-Rabin con GMP Publicado por: APOKLIPTICO en 30 Octubre 2010, 01:55 am Estuve haciendo pruebas, lo depuré a mas no poder y encontré un error en la función mpz_powm, que en vez de dar "n-1" da "1"...
Ese error ocurre cuando utilizo numeros un poco grandes. El problema debe de estar en la función, aunque me parece extraño. Título: Re: Test de primalidad Miller-Rabin con GMP Publicado por: soplo en 30 Octubre 2010, 23:39 pm Para facilitar la comprensión he modificado el código anterior (solo para este hilo) a fin de ver si encontramos donde está el error. He omitido las funciones GMP y las he escrito en C clásico con el único interes de ver si hay algún error lógico.
A mi me parece que hay algo del algoritmo que no he puesto bien y por eso no me funciona adecuadamente, pero es que no lo veo. Tal como está no funciona porque solo he cambiado textos, De hecho sé que faltan puntos y comas y tampoco están ni stdlib.h ni math.h pero da igual. Solo se trata de ver donde está el error para que no calcule bien. Ahi va Código: int miller_rabin ( long Num, int Comprobaciones ) Miller Rabin requiere que se encuentre un par de números R y S tal que satisfagan que (N-1)=R * 2^S. Además R debe ser impar. Num es el número a comprobar. NumDec es Num-1 Código: NumDec=Num-1; //NumDec=Num-1 Código: srand(time(NULL)) Lo de EsPrimo es un valor boleano. Si antes resultó que es divisible entre algún número primo que no haga el bucle y se vaya al final. Código: while ( Comprobaciones-- > 0 && EsPrimo) { ¿donde demonios está el error? Título: Re: Test de primalidad Miller-Rabin con GMP Publicado por: APOKLIPTICO en 30 Octubre 2010, 23:50 pm Yo lo compile y todo, el problema esta en GMP, por alguna razon la funcion del modulo exponencial, devuelve 1 cuando deberia devolver n-1.
|