Un número primo es un número entero mayor que 1 cuyos únicos factores son 1 y él mismo. Un factor es un número entero que se puede dividir uniformemente en otro número. Los primeros números primos son 2, 3, 5, 7, 11, 13, 17, 19, 23 y 29. Los números que tienen más de dos factores se llaman números compuestos. El número 1 no es ni primo ni compuesto.
Los números primos se pueden utilizar por varias razones. Por ejemplo, algunos tipos de criptografía utilizarán números primos.
Para cada número primo, por ejemplo "p", existe un número primo que es mayor que p, llamado p '. Esta prueba matemática, que fue demostrada en la antigüedad por el matemático griego Euclides, valida el concepto de que no existe un número primo "más grande". Como el conjunto de números naturales N = {1, 2, 3, ...} procede, los números primos generalmente se vuelven menos frecuentes y más difíciles de encontrar en un período de tiempo razonable.
Cómo determinar si un número es primo
Se puede usar una computadora para probar números extremadamente grandes para ver si son primos. Pero, debido a que no hay límite para cuán grande puede ser un número natural, siempre hay un punto en el que probar de esta manera se vuelve una tarea demasiado grande, incluso para las supercomputadoras más poderosas. Como ejemplo, el número primo más grande conocido en diciembre de 2018 fue 24,862,048 dígitos.
Se han formulado varios algoritmos en un intento de generar números primos cada vez más grandes. Por ejemplo, suponga que "n" es un número entero y aún no se sabe si n es primo o compuesto. Primero, saca la raíz cuadrada - o la potencia 1/2 - de n; luego redondee este número al siguiente número entero más alto y llame al resultado m. Luego, encuentre todos los siguientes cocientes:
qm = n / m
q (m-1) = n / (m-1)
q (m-2) = n / (m-2)
q (m-3) = n / (m-3)
. . .
q3 = n / 3
q2 = n / 2
El número n es primo si, y solo si, ninguna de las q, como se derivó anteriormente, son números enteros.
Primos de Mersenne y Fermat
Un número primo de Mersenne es un número que debe reducirse a la forma 2 n - 1, donde n es un número primo. Los primeros valores conocidos de n que producen números primos de Mersenne son donde n = 2, n = 3, n = 5, n = 7, n = 13, n = 17, n = 19, n = 31, n = 61, y n = 89.
Un número primo de Fermat es un número de Fermat que también es primo. Un número de Fermat F n tiene la forma 2 m + 1, donde m significa la potencia de 2, es decir, m = 2 n, y donde n es un número entero.
Números primos y criptografía
El cifrado siempre sigue una regla fundamental: el algoritmo, o el procedimiento real que se está utilizando, no necesita mantenerse en secreto, pero la clave sí. Los números primos pueden resultar muy útiles para crear claves. Por ejemplo, la fuerza del cifrado de clave pública / privada radica en el hecho de que es fácil calcular el producto de dos números primos elegidos al azar. Sin embargo, puede resultar muy difícil y llevar mucho tiempo determinar qué dos números primos se utilizaron para crear un producto extremadamente grande, cuando solo se conoce el producto.
En RSA (Rivest-Shamir-Adleman), un ejemplo bien conocido de criptografía de clave pública, siempre se supone que los números primos son únicos. Sin embargo, los números primos utilizados por el intercambio de claves Diffie-Hellman y los esquemas de criptografía Digital Signature Standard (DSS) se estandarizan y utilizan con frecuencia en un gran número de aplicaciones.