Contenido

• Al paso
• Método 1 de 4: intenta dividir
• Método 2 de 4: Uso del pequeño teorema de Fermat
• Método 3 de 4: uso de la prueba de Miller-Rabin
• Método 4 de 4: uso del teorema del resto chino
• Consejos
• Artículos de primera necesidad

Los números primos son números que solo son divisibles por sí mismos y se llaman 1 - otros números compuesto números. Cuando se trata de probar si un número es primo, existen varias opciones. Algunos de estos métodos son relativamente simples pero nada prácticos para números más grandes. Otras pruebas que se utilizan a menudo son en realidad algoritmos completos basados ​​en una probabilidad que a veces consideran erróneamente un número como primo. Continúe con el paso 1 para aprender a probarse a sí mismo si se trata de un número primo.

Al paso

Método 1 de 4: intenta dividir

Tratar de dividir es, con mucho, la forma más fácil de probar un número. Para números pequeños, suele ser también la forma más rápida. La prueba se basa en la definición de un número primo: un número es primo si solo es divisible por sí mismo y 1.

1. Suponer norte es el número que desea probar. Divida el número n por todos los números enteros divisibles posibles. Para números más grandes como n = 101, es muy poco práctico dividir por cualquier número entero posible menor que n. Afortunadamente, existen varios trucos para reducir la cantidad de factores a probar.
2. Determina si norte incluso. Todos los números pares son completamente divisibles por 2. Por lo tanto, si n es par, puedes decir que n es un número compuesto (y por lo tanto no es un número primo). Para determinar rápidamente si un número es par, solo debe prestar atención al último dígito. Si el último dígito es un 2, 4, 6, 8 o 0, entonces el número es par y no primo.
   • La única excepción a esta regla es el número 2 en sí mismo, que, debido a que es divisible por sí mismo y 1, también es primo. 2 es el único primo par.
3. Parte norte por cualquier número entre 2 y n-1. Debido a que un número primo no tiene factores distintos a sí mismo y 1, y debido a que los factores enteros son menores que su producto, verificar la divisibilidad de un número entero menor que ny mayor que 2 determinará si n es primo. Comenzamos después del 2 porque los números pares (múltiplos de 2) no pueden ser números primos. Esta está lejos de ser una forma eficiente de probar, como verá a continuación.
   • Por ejemplo, si quisiéramos usar este método para probar si 11 es primo o no, dividiríamos 11 entre 3, 4, 5, 6, 7, 8, 9 y 10, buscando una respuesta entera sin resto. Dado que ninguno de estos números encaja completamente en 11, podemos decir que 11 es uno es primordial.
4. Para ahorrar tiempo, solo pruebe hasta sqrt (norte), redondeado. Probar un número n comprobando todos los números entre 2 y n-1 puede llevar mucho tiempo rápidamente. Por ejemplo, si quisiéramos comprobar si 103 es primo con este método, tendríamos que dividir por 3, 4, 5, 6, 7 ... etc, ¡hasta 102! Afortunadamente, no es necesario realizar una prueba así. En la práctica, solo es necesario probar los factores entre 2 y la raíz cuadrada de n. Si la raíz cuadrada de n no es un número, redondea al entero más cercano y prueba a este número. Consulte a continuación para obtener una explicación:
   • Examinemos los factores de 100. 100 = 1 × 100, 2 × 50, 4 × 25, 5 × 20, 10 × 10, 20 × 5, 25 × 4, 50 × 2 y 100 × 1. Tenga en cuenta que después de 10 × 10, los factores son los mismos si eso por 10 × 10, solo entonces volteado. En general, podemos ignorar los factores de n mayores que sqrt (n) ya que son simplemente una continuación de factores menores que sqrt (n).
   • Probemos con un ejemplo. Si n = 37, entonces no necesitamos probar todos los números del 3 al 36 para determinar si n es primo. En cambio, solo necesitamos mirar los números entre 2 y sqrt (37) (redondeado hacia arriba).
     • sqrt (37) = 6.08 - vamos a redondear esto a 7.
     • 37 no es completamente divisible entre 3, 4, 5, 6 y 7, por lo que podemos afirmar con seguridad que es uno número primo es.
5. Para ahorrar aún más tiempo, solo usamos factores primos. Es posible hacer el proceso de prueba dividiendo aún más corto al no incluir aquellos factores que no son números primos. Por definición, todo número compuesto se puede expresar como el producto de dos o más números primos. Por lo tanto, no es necesario dividir el número n por un número compuesto; esto equivale a dividir entre números primos varias veces. Por lo tanto, podemos reducir aún más la lista de factores posibles a solo números primos menores que sqrt (n).
   • Esto significa que se pueden omitir todos los factores pares, así como los factores que son múltiplos de números primos.
   • Por ejemplo, intentemos determinar si 103 es primo o no. La raíz cuadrada de 103 es 11 (redondeado hacia arriba). Los números primos entre 2 y 11 son 3, 5, 7 y 11. 4, 6, 8 y 10 son pares y 9 es un múltiplo de 3, un número primo, por lo que podemos omitirlo. ¡Al hacer esto, hemos reducido nuestra lista de posibles factores a solo 4 números!
     • 103 no es completamente divisible por 3, 5, 7 u 11, por lo que ahora sabemos que 103 es uno número primo es.

Método 2 de 4: Uso del pequeño teorema de Fermat

En 1640, el matemático francés Pierre de Fermat propuso por primera vez un teorema (que ahora lleva su nombre) que puede ser muy útil para determinar si un número es primo o no. Técnicamente, la prueba de Fermat está destinada a verificar que un número es compuesto, en lugar de primo. Esto se debe a que la prueba puede mostrar con "certeza absoluta" que un número es compuesto, pero sólo una "probabilidad" de que un número sea primo. El pequeño teorema de Fermat es útil en situaciones en las que tratar de dividir no es práctico y cuando hay una lista de números disponibles que son excepciones al teorema.

1. Suponer norte el número es para probar. Utiliza esta prueba para determinar si un número n dado es primo. Sin embargo, como se señaló anteriormente, este teorema puede ocasionalmente caracterizar erróneamente algún compuesto como primo. Es importante tener esto en cuenta y comprobar su respuesta, que se explica a continuación.
2. Elija un número entero a entre 2 y norte-1 (incluido). El número entero exacto que elija no es importante. Dado que los parámetros para a incluyen 2 y n-1, también puede usarlos.
   • Un ejemplo: es 100 primo o no. Supongamos que tomamos 3 como valor de prueba, esto es entre 2 y n-1, por lo que es suficiente.
3. calcular a (modificación norte). La elaboración de esta expresión requiere algún conocimiento de un sistema matemático llamado matemáticas modulares. En matemática modular, los números vuelven a cero al alcanzar un cierto valor, también conocido como módulo. Puede pensar en esto como un reloj: eventualmente, la manecilla del reloj volverá a la 1 en punto después de las 12 en punto, no a las 13 en punto. El módulo se indica como (mod norte). Entonces, en este paso calcula a con un módulo de n.
   • Otro método es calcular a, luego dividirlo por n, luego usar el resto como respuesta. Las calculadoras especializadas con una función de módulo pueden ser muy útiles al dividir números grandes, porque pueden calcular inmediatamente el resto de una división.
   • Usando una calculadora de este tipo en nuestro ejemplo, podemos ver que 3/100 tiene un resto de 1. Entonces, 3 (mod 100) es 1.
4. Si calculamos esto a mano, usamos el exponente como formato corto. Si no tiene una calculadora con una función de módulo, use la notación con un exponente para facilitar el procedimiento para determinar el resto. Vea abajo:
   • En nuestro ejemplo, calculamos 3 con un módulo de 100. 3 es un número muy, muy grande - 515,377,520,732,011,331,036,461,129,765,621,272,702,107,522,001 - tan grande que resulta muy difícil trabajar con él. En lugar de usar la respuesta de 48 dígitos para 3, es mejor que la escribamos como un exponente, por lo que (((((((3)*3))))*3)). Recuerda que tomar el exponente de un exponente tiene el efecto de multiplicar los exponentes ((x) = x).
     • Ahora podemos determinar el resto. Empiece resolviendo ((((((3) * 3)))) * 3)) en el paréntesis interior y vaya saliendo, dividiendo cada paso por 100. Una vez que hayamos encontrado el resto, lo usaremos para el siguiente paso en lugar de la respuesta real. Vea abajo:
       • ((((((9) * 3)))) * 3)) - 9/100 no tiene resto, así que podemos continuar.
       • (((((27)))) * 3)) - 27/100 no tiene resto, así que podemos seguir adelante.
       • ((((729))) * 3)) - 729/100 = 7 R 29. Nuestro resto es 29. Continuamos con el siguiente paso, no 729.
       • ((((29=841)) * 3)) - 841/100 = 8 R 41. Usamos nuestro resto 41 nuevamente en el siguiente paso.
       • (((41 = 1681) * 3)) - 1681/100 = 16 R 81. Usamos nuestro resto 81 en el siguiente paso.
       • ((81*3 = 243)) - 243/100 = 2 R 43. Usaremos nuestro resto 43 en el siguiente paso.
       • (43 = 1849) - 1849/100 = 18 R 49. Usaremos nuestro resto 49 en el siguiente paso.
       • 49 = 2401 - 2401/100 = 24 R 1. Nuestro resto final es 1. En otras palabras, 3 (mod 100) = 1. ¡Tenga en cuenta que esta es la misma respuesta que calculamos en el paso anterior!
5. Averigua si a (modificación norte) = a (modificación norte). Si no es así, n es compuesto. Si es cierto, entonces n probablemente, (pero no estoy seguro) un número primo. Repetir la prueba con diferentes valores para a puede hacer que el resultado sea más seguro, pero hay números compuestos raros que satisfacen el teorema de Fermat todas valores de a. Estos se denominan números de Carmichael; el más pequeño de estos números es 561.
   • En nuestro ejemplo, 3 (mod 100) = 1 y 3 (mod 100) = 3.1 ≠ 3, entonces podemos decir que 100 es un número compuesto.
6. Utilice los números de Carmichael para estar seguro de su resultado. Saber qué números cumplen con la serie Carmichael antes de continuar puede ahorrarle muchas preocupaciones sobre si un número es primo o no. En general, los números de Carmichael son el producto de números primos individuales, donde para todos los números primos se sostiene que si p es un divisor de n, entonces también p-1 es un divisor de n-1. La lista en línea de números de Carmichael puede ser muy útil para determinar si un número es primo, usando el pequeño teorema de Fermat.
   
   

Método 3 de 4: uso de la prueba de Miller-Rabin

La prueba de Miller-Rabin funciona de la misma manera que el pequeño teorema de Fermat, pero trata mejor con números no estándar como los números de Carmichael.

1. Suponer norte es un número impar cuya primalidad queremos probar. Como en los métodos indicados anteriormente, n es la variable de la cual queremos determinar la primalidad.
2. Presión norte-1 en la forma 2 × D en el cual D es impar. El número n es primo si es impar. Entonces n - 1 debe ser par. Dado que n - 1 es par, se puede escribir como una potencia de 2 veces un número impar. Entonces, 4 = 2 × 1; 80 = 2 × 5; y así.
   • Suponga que queremos determinar si n = 321 es primo. 321 - 1 = 320, que podemos expresar como 2 × 5.
     • En este caso, n = 321 es un número adecuado. La determinación de n - 1 para n = 371 puede requerir un valor grande para d, lo que dificulta todo el proceso en una etapa posterior. 371 - 1 = 370 = 2 × 185
3. Elija cualquier número a entre 2 y norte-1. El número exacto que elija no importa, solo que debe ser menor que ny mayor que 1.
   • En nuestro ejemplo con n = 321, elegimos a = 100.
4. calcular a (modificación norte). Si a = 1 o -1 (mod norte), luego pasa norte la prueba de Miller-Rabin y es probablemente un número primo. Al igual que con el pequeño teorema de Fermat, esta prueba no puede determinar con absoluta certeza la primacía de un número, pero requiere pruebas adicionales.
   • En nuestro ejemplo con n = 321, a (mod n) = 100 (mod 321). 100 = 10,000,000,000 (mod 321) = 313. Usamos una calculadora especial, o el método abreviado con un exponente como se describió anteriormente, para encontrar el resto de 100/321.
     • Dado que no hemos obtenido 1 o -1, no podemos decir con certeza que n sea primo. Pero aún hay más por hacer, sigue leyendo.
5. Dado que el resultado no es igual a 1 o -1, calcule a, a, ... y así sucesivamente, hasta aD. Calcule a elevado a la potencia de d veces, hasta 2. Si cualquiera de estos es igual a 1 o -1 (mod norte), luego pasa norte las pruebas de Miller-Rabin y probablemente sea el mejor. Si ha determinado que n pasa la prueba, verifique su respuesta (consulte el paso a continuación). Si n falla alguna de estas pruebas, es una compuesto número.
   • Como recordatorio, en nuestro ejemplo, el valor de a es 100, el valor de s es 6 y d es 5. Continuamos probando como se muestra a continuación:
     • 100 = 1 × 10.
       • 1 × 10 (mod 321) = 64,64 ≠’ 1 o -1. Sigue adelante con calma.
     • 100 = 1 × 10.
       • 1 × 10 (mod 321) = 244.244 ≠ 1 o -1.
     • En este punto podemos detenernos. s - 1 = 6 - 1 = 5. Ahora hemos llegado a 4d = 2, y no hay potencias de 2 veces d por debajo de 5d. Dado que ninguno de nuestros cálculos respondió un 1 o -1, podemos decir que n = 321 uno compuesto número es.
6. Si norte pasa la prueba de Miller-Rabin, repita para los otros valores de a. Si ha encontrado que el valor de n podría ser primo, intente nuevamente con un valor aleatorio diferente para a para confirmar el resultado de la prueba. Si n es realmente primo, será verdadero para cualquier valor de a. Si n es un número compuesto, fallará para tres cuartas partes de los valores de a. Esto le da más certeza que el pequeño teorema de Fermat, donde ciertos los números compuestos (los números de Carmichael) pasan la prueba para cualquier valor de a.

Método 4 de 4: uso del teorema del resto chino

1. Elija dos números. Uno de los números no es primo y el segundo es el número que se está probando para determinar su primalidad.
   • "Número de prueba1" = 35
   • Número de prueba2 = 97
2. Elija dos puntos de datos mayores que cero y menores que TestNumber1 y TestNumber2, respectivamente. No pueden ser iguales entre sí.
   • Datos1 = 1
   • Datos2 = 2
3. Calcule el MMI (Matemático Multiplicativo Inverso) para el número de prueba1 y el número de prueba2
   • Calcular el MMI
     • MMI1 = Test Number2 ^ -1 Mod Test Number1
     • MMI2 = Test Number1 ^ -1 Mod Test Number2
   • Solo para números primos (habrá un resultado para números no primos, pero ese no es el MMI):
     • MMI1 = (TestNumber2 ^ (TestNumber1-2))% TestNumber1
     • MMI2 = (TestNumber1 ^ (TestNumber-2))% TestNumber2
   • Entonces:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. Cree una tabla binaria para cada MMI hasta Log2 del módulo
   • Para el MMI1
     • F (1) = Número de prueba 2% Número de prueba 1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% Número de prueba1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Número de prueba1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Número de prueba1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Número de prueba1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Número de prueba 1 = 1 * 1% 35 = 1
   • Calcular el logaritmo binario de TestNumber1 - 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úmero de prueba1% Número de prueba2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% Número de prueba2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Número de prueba2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Número de prueba2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% Número de prueba2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Número de prueba2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% Número de prueba2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Número de prueba2 = 35 * 35 mod 97 = 61
   • Calcular el logaritmo binario de TestNumber2 - 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. Calcular (Data1 * TestNumber2 * MMI1 + Data2 * TestNumber1 * MMI2)% (TestNumber1 * TestNumber)
   • Respuesta = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Respuesta = (2619 + 4270)% 3395
   • Respuesta = 99
6. Compruebe que "TestNumber1" no sea prime1
   • Calcular (Respuesta - Datos1)% Número de prueba1
   • 99 -1 % 35 = 28
   • Dado que 28 es mayor que 0, 35 no es primo
7. Compruebe si TestNumber2 es primo
   • Calcular (Respuesta - Datos2)% Número de prueba2
   • 99 - 2 % 97 = 0
   • Dado que 0 es igual a 0, 97 es un número primo potencial
8. Repita los pasos 1 a 7 al menos dos veces más.
   • Si el paso 7 es igual a 0:
     • Utilice un "TestNumber1" diferente si TestNumber1 no es primo.
     • Utilice otro TestNumber1 donde un TestNumber1 sea realmente primo. En este caso, los pasos 6 y 7 son iguales a 0.
     • Utilice diferentes puntos de datos para data1 y data2.
   • Si el paso 7 siempre es igual a 0, entonces la probabilidad de que el número 2 sea un número primo es muy alta.
   • Se sabe que los pasos del 1 al 7 son incorrectos en ciertos casos cuando el primer número no es primo y el segundo es un factor primo del número no primo "Test Number1". Funciona en todos los escenarios donde ambos números son primos.
   • La razón por la que se repiten los pasos del 1 al 7 es porque hay algunos escenarios en los que, incluso si TestNumber1 no es primo y TestNumber2 no es primo, cualquiera de los números del Paso 7 sigue siendo cero. Estas condiciones son raras. Al cambiar TestNumber1 a otro número no primo, si TestNumber2 no es primo, TestNumber2 ya no será igual a cero, en el paso 7. Excepto en el caso en el que "TestNumber1" es un factor de TestNumber2, los números primos siempre serán cero. paso 7.

Consejos

• Los 168 números primos debajo de 1000 son: 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
• Cuando tratar de dividir es más lento que los métodos más sofisticados, sigue siendo eficiente para números más pequeños. Incluso cuando se prueban números más grandes, no es raro verificar primero los números pequeños antes de cambiar a los métodos más avanzados.

Artículos de primera necesidad

• Papel, bolígrafo, lápiz y / o calculadora para hacer ejercicio