¿Cuál es el mejor algoritmo para verificar si un número es primo?

Probablemente no haya una manera fácil de hacer esto, pero podría usar el pequeño teorema de Fermat para descubrir la primalidad de un número con una pequeña posibilidad de obtener una respuesta incorrecta.

El teorema establece que para verificar si un número n es primo, haga la siguiente prueba:

Elija un número [matemática] b [/ matemática] tal que [matemática] 1 \ leq b Si [math] b ^ {n-1} \ mod {n} = 1 [/ math], entonces el número es primo.

Considere el ejemplo de un número primo [matemáticas] 17 [/ matemáticas]. Vamos a elegir [matemáticas] b = 3 [/ matemáticas]

Ahora, [matemática] 3 ^ {16} \ mod {17} [/ matemática] es igual a [matemática] 1 [/ matemática]. Por lo tanto, el número es primo.

Sin embargo, hay una pequeña posibilidad de falla para algunos números, estos se llaman Números de Carmichael y puede leer sobre ellos aquí – Número de Carmichael

Aquí hay un pequeño programa de Python para encontrar la primalidad de un número:

from random import randrange def fermat(n,tests):
"""Determine the primality of a number with a small chance of failure"""
#Depends on the number of tests provided
for x in range(tests):
if ((randrange(1,n))**(n-1))%n != 1:
return False
return True

from random import randrange def fermat(n,tests):
"""Determine the primality of a number with a small chance of failure"""
#Depends on the number of tests provided
for x in range(tests):
if ((randrange(1,n))**(n-1))%n != 1:
return False
return True

La respuesta realmente depende de muchos factores.

Primero de todo, el tamaño. Para números pequeños, la prueba de división funciona bastante bien. Verifique todos los números hasta [math] \ sqrt n [/ math] para la división. Si muchos de esos números necesitan ser probados por primalidad, se puede usar algún algoritmo de tamizado para encontrar la primalidad de todo el rango.

Para grandes [matemáticas] n [/ matemáticas], este método comienza a ser demasiado lento. Entonces necesitamos buscar algo mejor. Aquí, tenemos que tomar una decisión importante. ¿Qué queremos decir al verificar si un número es primo? ¿Lo hará una respuesta correcta con una probabilidad extremadamente alta ? Esto se debe a que los algoritmos probabilísticos para verificar la primalidad son mucho más rápidos que los deterministas. Un buen ejemplo rápido de un algoritmo probabilístico es la prueba de primalidad de Miller-Rabin, que da una respuesta con solo una [matemática] 4 ^ {- k} [/ matemática] probabilidad de estar equivocado cuando [matemática] k [/ matemática] potencial Se utilizan testigos de compostura. Tales algoritmos son suficientes para aplicaciones de la vida real.

Ahora, si realmente necesita un algoritmo determinista, vaya a la prueba de primitividad de curva elíptica o la prueba de primalidad AKS. Son mucho más lentos que los algoritmos probabilísticos, pero aún así son polinómicos y, por lo tanto, más rápidos que todos los métodos de fuerza bruta.

Además, si sabe que su número tiene alguna forma especial, existen algoritmos especializados que son más rápidos. Estas son la prueba de primalidad de Lucas-Lehmer (para los números de Mersenne: números de la forma [matemáticas] 2 ^ {p} -1 [/ matemáticas]), la prueba de Lucas-Lehmer-Riesel (para los números de la forma [matemáticas] k 2 ^ {n} -1 [/ math]), prueba de Pépin (para números de Fermat: números de la forma [math] 2 ^ {2 ^ n} + 1 [/ math]).

Probablemente la prueba de primalidad más utilizada se llama Miller-Rabin, y técnicamente es una suposición. Es una suposición increíblemente segura, pero su velocidad y eficiencia es una compensación con absoluta certeza. (Además, no dice nada sobre los números compuestos, excepto que no son primos). Es increíblemente rápido y no es un “atajo”. Es la cosa real.

(Para una certeza determinista, hay una variante más lenta de MR, y hay una prueba más nueva llamada AKS. En comparación con MR, es lenta, pero se considera un avance porque es infinitamente escalable).

Solo estoy agregando esta información porque las respuestas que ha recibido hasta ahora no son precisas. El más cercano hace referencia a FlT (que, por cierto, es mucho más importante para la historia de las matemáticas que FLT). Es la base de todas las pruebas de primalidad que usan “exponenciación modular”, incluido Miller-Rabin.

FlT dice que si N es un número primo, entonces un entero arbitrario elevado al exponente del número primo se divide por igual entre p sin ningún resto . (Si está interesado en por qué, vea aquí). Sin embargo, esto solo es cierto la mayoría de las veces, no todo el tiempo. El truco, para hacerlo más preciso, es probar múltiples enteros arbitrarios. Cuanto más pruebes, más preciso será el resultado.

Miller-Rabin lleva esto un paso más allá de una manera que puedo explicar, pero no entiendo completamente. Se ve en la misma igualdad, pero donde el exponente es un factor de N-1 y el entero que se expone se elige al azar. Este entero se llama testigo de la composición del número que se está probando. La prueba solo tiene que fallar solo una vez para que el número sea certificablemente compuesto. Alrededor del 75% de los enteros son testigos de la composición si el número es compuesto.

Si repite la prueba varias veces (10, 20 o 100 veces), la precisión de la prueba es del 99,99% de precisión. Técnicamente, todavía es una suposición, pero a menos que esté tratando de encontrar el próximo semiprime RSA con 1000 dígitos, no es algo de lo que deba preocuparse.

Si desea verificar solo un número N

1. El primero es el enfoque bruto para verificar si el número tiene exactamente 2 divisores 1 y se numera a sí mismo. Esto se puede hacer en tiempo lineal O (N)
2. Puede hacerlo en O (sqrt (N)) complejidad. Digamos que un número tiene algún divisor distinto de 1 y N dice a, entonces, si un miente antes de sqrt (N) otro mentirá después de sqrt (N), a * b = N. Por lo tanto, iteraremos hasta sqrt (N) y verificaremos que el no posee ningún divisor de este tipo.

Prueba de primalidad | Conjunto 1 (Introducción y método escolar) – GeeksforGeeks

3 Si desea usar la computadora para un conjunto grande de números, diga 10 ^ 6. Entonces N * sqrt (N) tendrá 10 ^ 9 operaciones y, por lo tanto, este enfoque no será el mejor enfoque en esta situación.

Para este preprocesamiento se realiza y todos los primos hasta 10 ^ 6 se pueden almacenar por separado.

Este enfoque se llama Tamiz o Eratóstenes Tamiz de Eratóstenes – GeeksforGeeks

Espero que hayas entendido el concepto si no lo preguntas en el comentario.

Mucho se ha escrito sobre las pruebas de primalidad. Que yo sepa, el algoritmo de ejecución más rápida es la prueba de primalidad AKS *: las versiones bien optimizadas se ejecutan en tiempo [matemático] O \ left (\ log (N) ^ 6 \ right) [/ math]. (Compare con verificar todos los divisores hasta [math] \ sqrt {N} [/ math], que por supuesto solo se ejecuta en [math] O \ left (\ sqrt {N} \ right) [/ math] para darse cuenta de lo increíble esto es.)

Hay pruebas probabilitísticas más rápidas, es decir, algoritmos que determinan si un número es primo o no con una probabilidad muy alta. La prueba de primalidad de Miller-Rabin es un buen ejemplo.

También vale la pena señalar que existen varias conjeturas en la teoría de números que, si se prueban, nos permitirían mostrar que ciertos algoritmos realmente funcionan como se desea y / o nos permitirían reducir el tiempo de cálculo. Por ejemplo, si la Hipótesis de Riemann generalizada es cierta, entonces hay una variante determinista de la prueba de Miller-Rabin que se ejecuta en [matemáticas] O \ izquierda (\ log (N) ^ 4 \ derecha) [/ matemáticas] tiempo.

* Para ser precisos, con esto me refiero al algoritmo que ha demostrado utilizar la menor cantidad de operaciones en el límite, ya que [matemática] N [/ matemática] tiende al infinito. Eso no significa que sea el algoritmo más rápido en la práctica , por al menos dos razones: 1) hay algoritmos que funcionan más rápido, pero simplemente no hemos demostrado que funcionen más rápido, y 2) hay algoritmos que funcionan más rápido en los rangos típicos de [matemáticas] N [/ matemáticas] que las personas realmente usan. Vea los comentarios para más detalles.

Escuché sobre esto recientemente.

Tamiz de Eratóstenes. Es un tamiz de números primos que marca todos los múltiplos de números primos como compuestos, iterativamente, comenzando desde 2. Es una de las formas más eficientes de encontrar números primos hasta un número dado.

Actualización: hay un método más rápido utilizado para verificar si un número es primo o no, derivado únicamente del Tamiz de Eratóstenes. Solo necesita probar si el número es divisible de 2 a la raíz cuadrada del número. Si la raíz cuadrada del número no es un número entero, puede redondearlo al siguiente número entero o verificar la divisibilidad hasta la raíz cuadrada del siguiente cuadrado perfecto.

Por ejemplo, 45, necesitará verificar si 45 es divisible por 3,4 .. así sucesivamente hasta 7 (raíz de 49, el cuadrado perfecto más cercano a 45). Esto reduce aún más los cálculos.

El algoritmo más fácil es el método tradicional con una pequeña modificación en las condiciones de verificación.

Comenzaré a verificar desde un valor inicial de 2 hasta “n / 2” donde ‘n’ es el número de entrada que se va a verificar.

Lo que hace es reducir el número de iteraciones requeridas a la mitad. Si se encuentra algún divisor, el bucle se rompe y muestra que no es un número primo. Si el bucle no se rompe, significa que no se ha encontrado ningún divisor y, por lo tanto, se denomina número primo. Aquí está el código:

Desafortunadamente, las pruebas de primalidad no son tan simples como las pruebas de divisibilidad. Existen algunos teoremas, pero para un número tan grande, sería aconsejable utilizar un enfoque de fuerza bruta, en el que se divide por cada primo menos que la raíz cuadrada del número. Si busca un método no iterativo para números pequeños, puede intentar,

1. Teorema de Wilson:
El teorema de Wilson establece que un número natural n > 1 es un número primo si:

Para un número tan grande como el que sugirió, encontrar el factorial sería una tarea muy grande.

2. El pequeño teorema de Fermat:
El pequeño teorema de Fermat establece que si p es un número primo, entonces para cualquier número entero a> 1

Suponiendo que elija el más pequeño a = 2, su exponente 89575035341 sería un número muy grande.

Si se supone que el número es x y tenemos que verificar si x es primo o no … entonces
paso1- encuentra el cuadrado perfecto más cercano que viene después de x
Paso 2: encuentra la raíz cuadrada de ese cuadrado perfecto, deja que la raíz cuadrada sea y
Paso 3: enumera todos los números primos hasta y y divide x entre cada uno de ellos.
Paso 4: si x divide alguno de ellos, no es primo
Por ej. Comprobar 155 es primo o no.
Paso 1: el cuadrado perfecto más cercano es 169
La raíz de Step2-sq es 13
Paso 3-primo no. Hasta 13 son 2,3,5,7,11 y 13
Paso4-155 se divide por 5 …
Por lo tanto, 155 no es un número primo.
Con algo de práctica, esta técnica puede ahorrar tiempo.

Otro algoritmo para int n: Aquí estoy escribiendo código en java donde estoy usando dos propiedades de primo no. :

• Cualquier no primo no. tiene un factor (> 1) menor o igual que su raíz cuadrada.
• Excepto 2 y 3, todos los demás números primos no. son de la forma 6k + 1 o 6k + 5 (o 6k-1 )

Números primos Teoría de números Pruebas de primalidad

public void prime (int n)
{
si (n == 2 || n == 3)
{
System.out.println (“Prime”);
regreso;
}
si (n% 6 == 1 || n% 6 == 5)
{
para (int i = 5; i {
si (n% i == 0)
{
System.out.println (“Not Prime”);
regreso;
}
}
System.out.println (“Prime”);
regreso;
}
System.out.println (“Not Prime”);
}

El tamiz de Eratóstenes es la forma más rápida de encontrar números primos de menos de 10 millones.

Así es como funciona el algoritmo:

1. Cree una matriz de enteros consecutivos de 2 a n : (2, 3, 4, …, n )
2. Inicialmente, sea p igual a 2, el primer número primo.
3. A partir de p , cuente en incrementos de p y marque cada uno de estos números mayor que p en la lista. Estos números serán 2 p , 3 p , 4 p , etc. tenga en cuenta que algunos de ellos ya pueden haber sido marcados.
4. Encuentre el primer número mayor que p en la lista que no está marcado. Si no hubo tal número, deténgase. De lo contrario, deje que p ahora sea igual a este número (que es el próximo primo) y repita desde el paso 3.

Cuando se completa el algoritmo, los números no marcados en la matriz son primos. Puede inicializar un conjunto booleano verdadero y luego marcar falso cada múltiplo. Entonces el valor correspondiente a verdadero son números primos.

Puedes encontrar el código aquí:

Tamiz de Eratóstenes – GeeksforGeeks

No hay formas triviales de saber determinísticamente que un número es primo. Para grandes números, definitivamente tendría que emplear un programa de computadora. Puede leer más sobre las pruebas en la prueba Primality.

Sin embargo, una buena manera de eliminar un número como no primo es el hecho de que todos los números primos tienen la forma 6K + 1 o 6K-1; donde K es cualquier número entero. Por lo tanto, cualquier número que no cumpla con este criterio no puede ser primo. Sin embargo, lo contrario no es cierto; Todos los números que cumplen con este criterio no son primos.

Una prueba de primalidad simple es la división de prueba : para comprobar si [math] n [/ math] es primo, verifique cada [math] k \ leq \ sqrt {n} [/ math] if [math] k [/ math ] divide [matemáticas] n [/ matemáticas]. Si no se encuentra un divisor, entonces [math] n [/ math] es primo.

La división de prueba es ineficiente para grandes [matemáticas] n [/ matemáticas] si los números se representan en una base no unaria; con [math] m [/ math] dígitos podemos escribir números hasta [math] 2 ^ {O (m)} [/ math]. Afortunadamente, existe un algoritmo de tiempo polinómico para la prueba de primalidad: se publicó en 2002. Consulte Prueba de primalidad es fácil.

Edición porque la pregunta cambió. Estás buscando una prueba de primalidad, y hay bastantes opciones. El mejor depende del tamaño del número y sus recursos. He escrito implementaciones de código abierto de todos los métodos mencionados aquí, excepto APR-CL, y ejecuto pruebas y pruebas de primalidad todos los días.

Primero, seamos súper prácticos. Tengo un número n, digamos 5777, y quiero saber si es primo, y estoy frente a una computadora. Algunos métodos simples:

Pari / GP: echo 'ispseudoprime(5777)' | gp -q echo 'ispseudoprime(5777)' | gp -q

Perl / ntheory: perl -Mntheory=:all -E 'say is_prime(5777)' (para entradas de> 64 bits, ajuste el número entre comillas)

WolframAlpha: abra Computational Knowledge Engine y escriba PrimeQ[5777]

OpenPFGW: pfgw64s -q'5777'

Todo esto funciona con entradas bastante grandes. Los primeros tres ejecutan varias pruebas de compostura con la esperanza de regresar rápidamente, luego ejecutan una prueba principal probable BPSW. El último solo ejecuta una prueba de Fermat, pero tiene la distinción de ser mucho más rápido una vez que la entrada supera los 10k dígitos. Los tres primeros también pueden hacer pruebas si le importa. Hay muchas otras utilidades e idiomas que pueden hacer esto.

Si está haciendo esto en su cabeza o en lápiz y papel, probablemente se limitará a la división de prueba. Use varias Reglas de divisibilidad, como las que se muestran en Wikipedia: Regla de divisibilidad. La mayoría de estos no son interesantes para una computadora (a menos que la entrada sea una cadena muy grande), pero los humanos tienden a encontrarlos bastante útiles. Luego pruebe la división por números primos (o cuotas o rueda mod-6 una vez que olvide los siguientes números primos) hasta la raíz cuadrada de la entrada. Hay otros métodos que la gente solía usar: puede encontrarlos en libros de matemáticas, utilizados principalmente en la década de 1970 o antes, buscando principalmente alguna forma de transformarse en una forma especial.

Si está preguntando acerca de la codificación, entonces la solución más fácil es usar la integrada en el lenguaje (Perl6, Pari / GP, Julia, …) o en una biblioteca común (muchas otras).

La solución de rendimiento más rápido es una combinación de estos métodos. La “más fácil” es la división de prueba pura, ya que solo toma unos minutos para escribir.

– División de prueba. Verifique la divisibilidad para todos los primos menores o iguales que sqrt (n). Para entradas más grandes, generalmente usamos un filtro simple (por ejemplo, probabilidades o 6k +/- 1 o una rueda mod-30) en lugar de usar primos, no solo es más simple sino que es * más rápido *. A menudo se usa con entradas más grandes como una verificación rápida usando solo unos pocos primos, donde realmente es una prueba de composición.

– Formas especiales. ¿Es un número de Mersenne? Luego filtro seguido de Lucas-Lehmer. Proth? LLR? Hay algunas formas numéricas que hacen que la prueba de primalidad sea muy fácil.

– Probables pruebas principales. Lo que generalmente usamos para entradas más grandes. Cuando se les da un primo, devuelven verdadero (“probablemente primo”). Cuando se les da un compuesto, devuelven verdadero (“probablemente primo”) o falso (“compuesto”). Por lo tanto, nunca mienten sobre los números primos, pero a veces no pueden verificar que un número sea compuesto. Los dos más utilizados en la práctica son Miller-Rabin y BPSW.

= Fermat: base para mucho trabajo, pero ya no se usa solo.

= Miller-Rabin: para entradas arbitrarias y bases seleccionadas al azar, esto tiene una probabilidad de falla de, como máximo, un 25% de posibilidades de no detectar un compuesto. Sabemos cómo hacer que esto sea determinista para las entradas de 64 bits, y para entradas más grandes podemos ejecutar suficientes pruebas para hacer que la probabilidad de error sea tan baja como sea necesaria.

= BPSW: publicado en 1980 en dos artículos cuyos autores tienen estas cuatro iniciales, combina dos pruebas: una prueba principal probable fuerte con base 2 (es decir, Miller-Rabin con base 2) y una prueba fuerte de Lucas con un método particular de elección de parámetros . Es extremadamente rápido, cuesta un poco menos de 3 pruebas de Miller-Rabin en total, y rechaza la mayoría de los compuestos después de solo la primera prueba. Verificado correcto para todas las entradas de 64 bits. No hay contraejemplos conocidos de ningún tamaño, incluso con académicos que trabajan diligentemente durante años para encontrar uno. Las dos pruebas tienen anti-correlación, lo que significa que las clases de residuos que tienen más probabilidades de pasar una de las pruebas son las que tienen menos probabilidades de pasar la otra. El software matemático más serio utiliza esta prueba.

= Lucas, Frobenius, Perrin, etc. Hay muchas pruebas principales probables. Las pruebas de Lucas se utilizan en la prueba BPSW, y algunas pruebas de Frobenius son prácticas.

– Pruebas BPSW y Miller-Rabin con conjuntos base conocidos son deterministas para entradas de 64 bits. Por lo tanto, no hay necesidad de complicarse realmente hasta que tengamos entradas de más de 20 dígitos. Incluso entonces, casi todos están satisfechos con la prueba principal probable, ya que es * mucho * más rápido que los métodos de prueba.

= Teorema de Wilson. Terriblemente poco práctico, pero un teorema interesante. No uses esto.

= División de prueba. Tiempo exponencial, no práctico pasado ~ 25 dígitos.

= Método de Leibniz usando binomios, descubierto alrededor de 1670, que es lo que recomienda Shreyash. Numberphile tiene un video sobre esto y lo llama AKS, que no es. Es un tiempo exponencial y terriblemente lento. Más lento que la división de prueba. No uses esto.

= Prueba de Miller. Ejecute pruebas de Miller-Rabin con al menos el 25% de las bases. Interesante, pero muy lento. Hay otra variante que es mucho más rápida y requiere pruebas como máximo 2 * (log n) ^ 2 bases. Sin embargo, el paso 1 del algoritmo es “probar la hipótesis de Riemann generalizada”, lo cual es un poco molesto.

= AKS. Tiempo polinómico determinista sin supuestos no comprobados. Maravilloso, verdad? También muy, muy lento en la práctica. En serio, no uses esto. Me estoy burlando de esto principalmente porque la gente lo sigue recomendando en los foros, lo que nunca harían si realmente intentaran * usarlo *.

= Métodos BLS75. Estado del arte en 1975, y todavía funciona hoy para números relativamente pequeños (por ejemplo, menos de 70 dígitos). Requiere factorización parcial. Más rápido que AKS para números de menos de 100 dígitos. Otorga un certificado de primalidad que otra persona puede verificar en muy poco tiempo.

= APR-CL. Tiempo sub-exponencial determinista. El exponente es más pequeño que AKS para cualquier entrada que termine el cálculo en billones de años. Pari / GP usa esto, y hay una buena implementación de código abierto. Rápido en la práctica. El único inconveniente es que, como AKS, no hay certificado. Simplemente dice “prime” o “composite” después de agitarse.

= ECPP. Curva elíptica Prueba de primalidad. Rápido. Algoritmo aleatorizado, ya que siempre devolverá una respuesta correcta, pero el tiempo necesario es heurístico (en la práctica durante más de 15 años funciona exactamente como esperamos). Esto se utiliza para la mayoría de las pruebas muy grandes (más de 10k dígitos). Puede dar un certificado que se pueda verificar de forma independiente. Una excelente implementación gratuita y una buena implementación de código abierto.

La regla de un número para ser primo es que no es divisible por ningún número excepto el 1 y el número mismo.

• Consultar arrendamiento dígito significativo.

• Por ejemplo, el número es 132.
• Entonces arrendar dígito significativo es 2.

1. Para el número superior a 7 si el número significativo de arrendamiento es un número par o 5, podemos decir que ese número es divisible por 2 o 5. No es un número primo.
2. Si la suma de todos los dígitos en número es divisible por 3, entonces no es un número primo.
3. Si número es multiplicidad de número primo, entonces tampoco es número primo.
4. ¡Al verificar las condiciones anteriores, podemos decir fácilmente si un número dado es primo o no!

• Otro método

• El número es el 11.
• Deberíamos verificar cada número del 2 al [(11-1) / 2] si es divisible o no.

Si el número no es divisible en este rango, entonces es el número primo.

Este método es eficiente para números pequeños, pero para verificar números grandes se puede aplicar la regla mencionada anteriormente.

Todas las respuestas existentes parecen apuntar a algunos algoritmos que son más adecuados para que las computadoras los ejecuten. Tengo la sensación de que la pregunta se refiere a una situación en la que, por ejemplo, en un examen, en algún momento uno tiene que calcular manualmente la primalidad de un número “enorme”. Y aquí, supongo que ‘enorme’ es un término relativo, como en, quizás 5 a 7 dígitos, no cientos de dígitos.

Entonces … para hacer esto manualmente:
1. Como alguien sugirió, simplemente marque dividiendo por cada primo hasta sqrt (N). Una ligera mejora en eso sería usar una prueba de divisibilidad, en lugar de ejecutar una división completa cada vez.
Cómo construir una prueba de divisibilidad para un divisor arbitrario es … un tema en sí mismo, pero aquí hay una ilustración rápida: un número 10a + b es divisible por 7, si-y-solo-si 50a + 5b también es, si- y solo si a + 5b también lo es. Aquí ‘b’ representa el dígito del lugar de las unidades, y ‘a’ representa la porción restante a partir del lugar de las decenas, respectivamente.
Entonces, por ejemplo, para verificar 32291, es suficiente verificar 3229 + 5 * 1 = 3234, o 323 + 5 * 4 = 343, o 34 + 5 * 3 = 49; que es claramente divisible por 7, por lo tanto, también es 32291.
(Espero que ayude … fue breve pero preciso; y puede hacer algo similar para cualquier divisor principal que no sea 2 y 5. Para obtener más detalles técnicos, busque ecuaciones de diofantina)

2. En caso de que un número sea compuesto, pero sus factores estén muy cercanos entre sí, típicamente cerca de sqrt (N), entonces el método 1 anterior tomará demasiado tiempo para alcanzar los factores. En este caso, el método de factorización de Fermat podría alcanzar los factores mucho más rápido.
Básicamente, si n = pq, donde n es impar, entonces p y q también son impares, entonces considere el ‘punto medio’ de p y q, es decir: a = (p + q) / 2, y la distancia del punto medio desde valor, es decir, b = (pq) / 2.
Entonces obtenemos p = a + b, y q = ab; entonces n = (a + b) (ab) = a ^ 2 – b ^ 2.
Entonces a ^ 2 – n = b ^ 2. Si puedes encontrar a y b, entonces puedes encontrar la factorización n = pq.
Entonces … el método es seguir probando valores para a, comenzando desde sqrt (n) hacia arriba. En cada caso, encuentre un ^ 2 – n, que inicialmente será pequeño y fácil de verificar si es un cuadrado perfecto o no. Si los factores p y q están ubicados entre sí, puede ver que b es pequeño, por lo que debería poder encontrar los factores con bastante rapidez.

3. Idealmente, una combinación de alternar entre los métodos 1 y 2 es mejor; ya que no se sabe directamente si los factores, si existen, son pequeños o grandes.

Para números de hasta 10 dígitos, puede probar el algoritmo normal de fuerza bruta: pruebe todos los divisores hasta su raíz cuadrada. Como efecto secundario, también lo tendrá en cuenta si no fuera primo.
Para números más grandes, puede acceder a otros algoritmos de comprobación de primalidades (no a lápiz y papel, lo siento), que pueden ser implementados por computadoras o incluso teléfonos que le dan una respuesta en menos de un segundo cuando el número tiene una longitud de hasta 50 dígitos ( depende). Y para cualquier número normal razonablemente rápido.

AKS: propósito general y polinomio (no muy rápido pero aún más rápido que los sub-exponenciales)

Puede verificar que un número sea compuesto verificando si 2 ^ (n-1)% n no es igual a 1. Aunque esto no es cierto para los pseudo primos y los números de Carmichael.

2 ^ 12% 13 = 1

3 ^ 12% 13 = 1

Para el número de Carmichael, a veces puede descubrir que no es primo utilizando el método n / 2 para diferentes valores de primos como base y verificando si los resultados son iguales a n-1. Este método también funciona para pseudoprimos fuertes. Cambiar la base generalmente funciona para pseudoprimos débiles.

1729 es un número de Carmichael

3 ^ 1728% 1729 = 1

3 ^ 864% 1729 = 1

3 ^ 432% 1729 = 1

…

3 ^ 27% 1729 = 664

mientras que un primo conocido como 23

2 ^ 22% 23 = 1

2 ^ 11% 23 = 1

3 ^ 11% 23 = 1

5 ^ 11% 23 = 22

que es igual a n-1

Tamiz de Eratóstenes: para generar primos

Para validar un número muy grande como primo, genere los primos usando Tamiz de Eratóstenes hasta el primo más pequeño mayor que la raíz cuadrada del número. Luego validar prime.