Encontrar el primer número mayor que N es un primo relativo a M

Question

No estoy seguro de si esta pregunta es el más adecuado para las matemáticas de cambio. Ya lo he intentado en stackoverflow sin suerte, así que espero que vuestras mentes brillantes será más útil.

Así que, básicamente, el azulejo dice todo. Los números no son demasiado grandes (por lo tanto, esto probablemente no es muy interesante para la gente normal aquí :)). El máximo de M es 2 * 10 ^ 63 y N es ~0.61 * M.

He hecho un pequeño programa para propósitos de prueba que se inicia a partir de N + 1, realiza una simple Euclidiana GCD, y si no son los números relativos de los números primos incrementamos N.

Me gustaría saber, ¿hay alguna solución mejor. Esto se ve muy trivial, y tal vez va a ser lo suficientemente rápido, pero me gustaría saber es que hay algo mejor.

También, si una respuesta para la mencionada pregunta es No, me gustaría saber ¿cuál es el peor caso para el algoritmo dado.

Corrí una prueba que va a realizar el procedimiento antes descrito algoritmo en algunos números al azar, y hasta ahora el resultado se encuentra siempre en menos de 30 iteraciones.

Gracias.

Answer 1

El número de enteros positivos menores que $M$ y relativamente primer a $M$ está dada por Euler totient función de $\varphi(M)$. La siguiente desigualdad se cumple para todos los $M>2$: $$ \varphi(M)>\frac{M}{e^\gamma\log\log M+\frac{3}{\log\log M}},\quad e^\gamma=1.7810\dots $$ En promedio, su algoritmo debe encontrar la solución en la mayoría de los $e^\gamma\log\log N$ iteraciones.

Para acelerar los cálculos, se puede encontrar un par de pequeños primos $p$ dividiendo $M$, y realizar el Euclidiana MCD sólo a los candidatos, que no son divisibles por los números primos. Por ejemplo, si $M$ es incluso, usted debe tratar sólo impar de candidatos. Esto será muy útil si usted tiene que hacer los cálculos para una fija $M$ y muchos diferentes $N$'s.