Creo que el enfoque más directo es implementar la prueba de Miller Rabin y luego intentar números consecutivos hasta encontrar un número primo. El número de candidatos que debe probar antes de encontrar un primo es proporcional al número de dígitos en el número con el que comienza (según el teorema del número primo), por lo que no tendrá que esperar mucho. Dependiendo de su perspectiva filosófica, podría molestarle que se trate de un algoritmo aleatorio, pero a efectos prácticos funciona muy bien.
Miller-Rabin es bastante fácil de implementar desde cero, y es casi seguro que sea lo suficientemente eficiente para sus propósitos. Aquí hay un ejemplo de implementación rápida y sucia en Python.
importar al azar
- ¿Cuál sería la relación más efectiva entre las matemáticas y la programación en educación?
- ¿Cómo podemos encontrar esos enteros cuyo primer y último dígito son iguales entre dos números dados?
- ¿Cuántos arreglos de piezas de ajedrez en un tablero de ajedrez hay, suponiendo que las piezas lleguen a sus posiciones mediante movimientos legales?
- ¿Debo dejar de tomar cursos de teoría en Matemáticas / CS teórico, etc.?
- Cómo hacer una forma generalizada a partir de un conjunto dado de expresiones (pasos / algoritmo de deseo)
# Determina si a es testigo de Miller-Rabin de n
def is_witness (a, n):
q = n-1
k = 0
mientras q% 2 == 0:
q / = 2
k + = 1
b = pow (a, q, n)
si b == 1: devuelve False
para i en xrange (k):
si b == n-1: devuelve False
b = b * b% n
volver verdadero
# Prueba de Miller-Rabin, con 100 ensayos por defecto
def is_prime (n, ensayos = 100):
para i en xrange (ensayos):
a = random.randrange (1, n)
if is_witness (a, n): devuelve False
volver verdadero
def next_prime (n):
mientras que no (is_prime (n)): n + = 1
volver n
En mi máquina, esto puede decirme el primer primo después de [matemáticas] 10 ^ {100} [/ matemáticas] en menos de un segundo (es [matemáticas] 10 ^ {100} +267 [/ matemáticas], si usted es curioso). Hay muchas maneras de hacer que esto sea más eficiente, por supuesto (por ejemplo: no hay necesidad de probar números pares; 100 intentos es mucho más de lo que necesita estar seguro de que un número es primo; un lenguaje compilado sería más rápido).
Un lugar al que puede ir para leer sobre buenos algoritmos para esto es la documentación de Sage. Sage tiene una función incorporada “next_prime” que bien podría usar más métodos de vanguardia de los que he descrito. No estoy seguro de qué método utiliza.
