¿Cuál es la forma más rápida de conseguir el próximo número Carmichael?

Question

Un número de Carmichael es un número compuesto $N$ , de tal manera que $a^{N-1}\equiv 1\mod N$ es válida para cada $a$ coprima a $N$ . $N$ es un número de Carmichael si

• $N$ es impar y libre de cuadrados
• $N$ tiene al menos tres factores primos distintos
• Para cada factor primo $p|N$ tenemos $p-1|N-1$

Un número entero positivo $M$ se da.

¿Cómo puedo encontrar eficientemente el menor número de Carmichael $N\ge M$ ?

Por ejemplo, el número Carmichael más pequeño por encima de $10^{10}$ es $$10017089857=73\cdot163\cdot577\cdot1459$$

Busco un método más eficaz que la fuerza bruta, algo así como una criba de Carmichael. ¿Alguna idea?

Answer 1

No creo que haya una manera mucho mejor de encontrar eficientemente un número específico de Carmichael. En realidad, los cálculos realizados en OEIS por Pinch lista todos los números de Carmichael hasta $1713045574801$ . Así que $10^{10}$ no es un problema.
Por otro lado, se puede encontrar un límite superior fácil para el menor número de Carmichael por encima de $10^{10}$ utilizando el criterio de Chernick: si $k$ es un número entero positivo tal que $6k + 1, 12k + 1$ y $18k + 1$ son todos primos entonces el producto $$ n = (6k + 1)(12k + 1)(18k + 1) $$ es un número de Carmichael. Para $k=195$ el criterio se aplica, porque $6\cdot 195+1$ , $12\cdot 195+1$ y $18\cdot 195+1$ son todos primos, por lo que $f(195)=9624742921$ es un límite inferior para el mayor número de Carmichael por debajo de $10^{10}$ (que es $9999109081$ ). Para un número de Carmichael superior a $10^{10}$ podemos tomar $k=206$ para que $11346205609$ es un número de Carmichael por encima de $10^{10}$ . Por supuesto, esto no será suficiente para encontrar eficazmente un número específico de Carmichael como se ha dicho.