Contenido

• Pasos
• Parte 1 de 3: Pruebas de simplicidad
• Parte 2 de 3: Cómo funcionan las pruebas de simplicidad
• Parte 3 de 3: Uso del teorema del resto chino
• Consejos
• Qué necesitas

Los números primos son números que son divisibles solo por sí mismos y por 1. Todos los demás números se denominan números compuestos. Hay muchas formas de determinar si un número es primo y todas tienen sus propias ventajas y desventajas. Por un lado, algunos de los métodos son muy precisos, pero son bastante complejos si se trata de números grandes. Por otro lado, existen formas mucho más rápidas, pero pueden conducir a resultados incorrectos. La elección del método apropiado depende de qué tan grandes sean los números con los que esté trabajando.

Pasos

Parte 1 de 3: Pruebas de simplicidad

Nota: en todas las fórmulas norte indica el número que se va a comprobar.

1. 1 Enumeración de divisores. Es suficiente para dividir norte a todos los números primos del 2 al valor redondeado (${ Displaystyle { sqrt {n}}}$).
2. 2 El pequeño teorema de Fermat. Advertencia: a veces, la prueba identificará falsamente números compuestos como primos, incluso para todos los valores de a.
   • Elijamos un número entero atal que 2 ≤ a ≤ n - 1.
   • Si a (mod n) = a (mod n) entonces el número probablemente sea primo. Si no se satisface la igualdad, el número n es compuesto.
   • Verifique la igualdad dada para múltiples valores apara aumentar la probabilidad de que el número que se está probando sea realmente primo.
3. 3 Prueba de Miller-Rabin. Advertencia: a veces, aunque raras veces, para varios valores de a, la prueba identificará falsamente los números compuestos como primos.
   • Encuentre las cantidades syd tales que ${ Displaystyle n-1 = 2 ^ {s} * d}$.
   • Seleccione un número entero a en el rango 2 ≤ a ≤ n - 1.
   • Si a = +1 (mod n) o -1 (mod n), entonces n probablemente sea primo. En este caso, vaya al resultado de la prueba. Si la igualdad no se mantiene, vaya al siguiente paso.
   • Cuadra tu respuesta${ Displaystyle a ^ {2d}}$). Si obtiene -1 (mod n), entonces n es probablemente un número primo. En este caso, vaya al resultado de la prueba. Si la igualdad falla, repita (${ Displaystyle a ^ {4d}}$ y así sucesivamente) hasta ${ Displaystyle a ^ {2 ^ {s-1} d}}$.
   • Si en algún paso después de elevar al cuadrado un número que no sea ${ Displaystyle pm 1}$ (mod n), obtuviste +1 (mod n), por lo que n es un número compuesto. Si ${ Displaystyle a ^ {2 ^ {s-1} d} neq pm 1}$ (mod n), entonces n no es primo.
   • Resultado de la prueba: si n pasa la prueba, repítala para otros valores apara aumentar la confianza.

Parte 2 de 3: Cómo funcionan las pruebas de simplicidad

1. 1 Enumeración de divisores. Por definición, el número norte es simple solo si no es divisible entre 2 y otros números enteros excepto 1 y él mismo. La fórmula anterior le permite eliminar pasos innecesarios y ahorrar tiempo: por ejemplo, después de verificar si un número es divisible por 3, no es necesario verificar si es divisible por 9.
   • La función floor (x) redondea x al número entero más cercano menor o igual que x.
2. 2 Aprenda sobre aritmética modular. La operación "x mod y" (mod es una abreviatura de la palabra latina "módulo", es decir, "módulo") significa "dividir x entre y y encontrar el resto". En otras palabras, en aritmética modular, al alcanzar un cierto valor, que se llama módulo, los números "se vuelven" a cero nuevamente. Por ejemplo, el reloj cuenta atrás con el módulo 12: muestra 10, 11 y 12 horas, y luego vuelve a 1.
   • Muchas calculadoras tienen una tecla mod. El final de esta sección le muestra cómo calcular manualmente esta función para números grandes.
3. 3 Conozca las trampas del pequeño teorema de Fermat. Todos los números para los que no se cumplen las condiciones de prueba son compuestos, pero el resto de los números son solo probablemente son simples. Si desea evitar resultados incorrectos, busque norte en la lista de "números de Carmichael" (números compuestos que satisfacen esta prueba) y "números pseudoprime de Fermat" (estos números cumplen las condiciones de prueba solo para algunos valores a).
4. 4 Si es conveniente, utilice la prueba de Miller-Rabin. Aunque este método es bastante engorroso para los cálculos manuales, a menudo se usa en programas de computadora. Proporciona una velocidad aceptable y menos errores que el método de Fermat. Un número compuesto no se tomará como número primo si se realizan cálculos para más de ¼ de valores. a... Si eliges aleatoriamente diferentes valores a y para todos ellos la prueba dará un resultado positivo, podemos asumir con un grado bastante alto de confianza que norte es un número primo.
5. 5 Para números grandes, use aritmética modular. Si no tiene una calculadora mod a mano, o la calculadora no está diseñada para manejar números tan grandes, use propiedades de potencia y aritmética modular para facilitar los cálculos. A continuación se muestra un ejemplo de ${ Displaystyle 3 ^ {50}}$ mod 50:
   • Vuelva a escribir la expresión en una forma más conveniente: ${ Displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50. Los cálculos manuales pueden requerir más simplificaciones.
   • ${ Displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50 = ${ Displaystyle (3 ^ {25}}$ mod 50 ${ Displaystyle * 3 ^ {25}}$ mod 50) mod 50. Aquí tomamos en cuenta la propiedad de la multiplicación modular.
   • ${ Displaystyle 3 ^ {25}}$ mod 50 = 43.
   • ${ Displaystyle (3 ^ {25}}$ mod 50 ${ Displaystyle * 3 ^ {25}}$ mod 50) mod 50 = ${ Displaystyle (43 * 43)}$ mod 50.
   • ${ displaystyle = 1849}$ mod 50.
   • ${ displaystyle = 49}$.

Parte 3 de 3: Uso del teorema del resto chino

1. 1 Elija dos números. Uno de los números debe ser compuesto y el otro debe ser exactamente el que desea probar por simplicidad.
   • Número1 = 35
   • Número2 = 97
2. 2 Seleccione dos valores que sean mayores que cero y, respectivamente, menores que los números Número1 y Número2. Estos valores no deben ser iguales.
   • Valor1 = 1
   • Valor2 = 2
3. 3 Calcule el MMI (Matemático Multiplicativo Inverso) para Número1 y Número2.
   • Calcular MMI
     • MMI1 = Number2 ^ -1 Mod Number1
     • MMI2 = Número1 ^ -1 Mod Número2
   • Solo para números primos (esto le dará un número para números compuestos, pero no será su MMI):
     • MMI1 = (Número2 ^ (Número1-2))% Número1
     • MMI2 = (Número1 ^ (Número2-2))% Número2
   • Por ejemplo:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. 4 Cree una tabla para cada MMI hasta los módulos log2:
   • Para MMI1
     • F (1) = Número2% Número1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% Número1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Número1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Número1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Número1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Número1 = 1 * 1% 35 = 1
   • Calcular números emparejados 1-2
     • 35-2 = 33 (10001) base 2
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • MMI1 = F (33) = 1 * 27 mod 35
     • MMI1 = 27
   • Para MMI2
     • F (1) = Número1% Número2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% Número2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Número2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Número2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% Número2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Número2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% Número2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Número2 = 35 * 35 mod 97 = 61
   • Calcule el número emparejado 2 - 2
     • 97 - 2 = 95 = (1011111) base 2
     • MMI2 = (((((F (64) * F (16)% 97) * F (8)% 97) * F (4)% 97) * F (2)% 97) * F (1)% 97)
     • MMI2 = ((((35 * 35)% 97) * 61)% 97) * 35% 97) * 61% 97) * 35% 97)
     • MMI2 = 61
5. 5 Calcular (Valor1 * Número2 * MMI1 + Valor2 * Número1 * MMI2)% (Número1 * Número2)
   • Respuesta = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Respuesta = (2619 + 4270)% 3395
   • Respuesta = 99
6. 6 Comprueba que Number1 no sea primo
   • Calcular (Respuesta - Valor1)% Número1
   • 99 – 1 % 35 = 28
   • Dado que 28 es mayor que 0, 35 no es un número primo.
7. 7 Compruebe que Número2 sea primo.
   • Calcular (Respuesta - Valor2)% Número2
   • 99 – 2 % 97 = 0
   • Dado que 0 es 0, lo más probable es que 97 sea un número primo.
8. 8 Repita los pasos del 1 al 7 al menos dos veces más.
   • Si obtiene 0 en el paso 7:
     • Utilice un Número 1 diferente si Número 1 no es primo.
     • Utilice otro Número1 si Número1 es primo. En este caso, debería obtener 0 en los pasos 6 y 7.
     • Utilice diferentes Significado1 y Significado2.
   • Si en el paso 7 obtiene constantemente 0, es muy probable que el número 2 sea primo.
   • Los pasos del 1 al 7 pueden dar como resultado un error si Número1 no es primo y Número2 es un divisor de Número1. El método descrito funciona en todos los casos cuando ambos números son primos.
   • La razón por la que necesita repetir los pasos del 1 al 7 es porque en algunos casos, incluso si el Número 1 y el Número 2 no son primos, en el paso 7 obtendrá 0 (para uno o ambos números). Esto rara vez sucede.Elija otro Número1 (compuesto), y si Número2 no es primo, entonces Número2 no será igual a cero en el paso 7 (excepto en el caso en el que Número1 es un divisor de Número2; aquí los números primos siempre serán iguales a cero en el paso 7).

Consejos

• Números primos del 168 al 1000: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79 , 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211 , 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359 , 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509 , 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673 , 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853 , 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997.
• Aunque la prueba de fuerza bruta es una prueba tediosa cuando se trabaja con números grandes, es bastante eficiente para números pequeños. Incluso en el caso de números grandes, comience probando divisores pequeños y luego pase a métodos más sofisticados para verificar la simplicidad de los números (si no se encuentran divisores pequeños).

Qué necesitas

• Papel, bolígrafo o computadora