¿Cómo saber Si un número es primo?
Utilizar el teorema chino del resto
Elige dos números. Elige dos puntos de datos que sean mayores a cero y menores que primo1 y primo2 respectivamente. Calcula el inverso multiplicativo (IM) de los números primo1 y primo2. Crea una tabla de conversión binaria para cada IM hasta llegar al log2 del módulo. Calcula (dato1 * primo2 * IM1 + dato2 * primo1 * IM2) % (primo1 * primo2). Verifica que “primo1” no sea un número primo. Verifica si primo2 es un número primo. Repite los pasos del 1 al 7 por lo menos unas dos veces más.
Uno de ellos no debe ser primo, mientras que el otro debe ser el que necesitas analizar para detectar su primalidad.   “primo1” = 35 primo2 = 97 No pueden ser iguales.   dato1 = 1 dato2 = 2 Calcula el IM:  IM1 = primo2 ^ -1 mod primo1 IM2 = primo1 ^ -1 mod primo2   Solo en el caso de los números primos (obtendrás un número para los números compuestos, pero no será su IM):  IM1 = (primo2 ^ (primo1-2)) % primo1 IM2 = (primo1 ^ (primo2-2)) % primo2   Por ejemplo:  IM1 = (97 ^ 33) % 35 IM2 = (35 ^ 95) % 97 Para IM1:  F(1) = primo2 % primo1 = 97 % 35 = 27 F(2) = F(1) * F(1) % primo1 = 27 * 27 % 35 = 29 F(4) =  F(2) * F(2) % primo1 = 29 * 29 % 35 = 1 F(8) = F(4) * F(4) % primo1 = 1 * 1 % 35 = 1 F(16) =F(8) * F(8) % primo1 = 1 * 1 % 35 = 1 F(32) =F(16) * F(16) % primo1 = 1 * 1 % 35 = 1   Realiza la conversión binaria de primo1 - 2  35 -2 = 33 (10001) base 2 IMI1 = F(33) = F(32) * F(1) mod 35 IM1 = F(33) = 1 * 27 mod 35 IM1 = 27   Para IM2:  F(1) = primo1 % primo2 = 35 % 97 = 35 F(2) = F(1) * F(1) % primo2 = 35 * 35 mod 97 = 61 F(4) = F(2) * F(2) % primo2 = 61 * 61 mod 97 = 35 F(8)  = F(4) * F(4) % primo2 = 35 * 35 mod 97 = 61 F(16) = F(8) * F(8) % primo2 = 61 * 61 mod 97 = 35 F(32)  = F(16) * F(16) % primo2 = 35 * 35 mod 97 = 61 F(64)  = F(32) * F(32) % primo2 = 61 * 61 mod 97 = 35 F(128) = F(64) * F(64) % primo2 = 35 * 35 mod 97 = 61   Realiza la conversión binaria de primo2 - 2  97 - 2 = 95 = (1011111) base 2 IM2= (((((F(64) * F(16) % 97) * F(8) % 97) * F(4) % 97) * F(2) % 97) * F(1) % 97) IM2= (((((35 * 35) %97) * 61) % 97) * 35 % 97) * 61 % 97) * 35 % 97) IM2= 61 Respuesta = (1 * 97 * 27 + 2 * 35 * 61) % (97 * 35) Respuesta = (2619 + 4270) % 3395 Respuesta = 99 Calcula (respuesta - dato1) % primo1. 99 -1 % 35 = 28. Como 28 es mayor que 0, significa que 35 no es un número primo. Calcula (respuesta - data2) % primo2 99 - 2 % 97 = 0 Como 0 es igual a 0, significa que 97 probablemente sea un número primo. Si en el paso 7 obtienes un 0:  Utiliza un “primo1” diferente, donde primo1 no es un número primo. Utiliza un primo1 diferente, donde primo1 no es un número real. En este caso, los pasos 6 y 7 deben ser iguales a 0. Utiliza diferentes puntos de datos para dato1 y dato2.   Si el paso 7 siempre da 0 como resultado, existe una probabilidad muy grande de que primo2 sea un número primo. En algunos casos, los pasos del 1 al 7 pueden fallar si el primer número no es primo y el segundo es un factor del número compuesto “primo1”.  Funciona en todos los casos donde ambos números son primos. El motivo por el que se repiten los pasos del 1 al 7 es debido a que hay algunas ocasiones en que, aun cuando primo1 y primo2 sean compuestos, el paso 7 sigue dando como resultado 0, ya sea para uno o para ambos números. No obstante, estas circunstancias son raras. Al convertir primo1 en un número compuesto distinto, si primo2 no es primo, este sin duda será igual a cero en el paso 7. Exceptuando en el caso donde “primo1” es un factor de primo2, los números primos siempre serán iguales a cero en el paso 7.
Chinese Remainder Theorem Test