Polinomios vs Números primos

Cuando se estudia a los números primos, llegamos a la pregunta ¿Qué tan frecuente aparecen estos números especiales?

Una simple pregunta  llevo a desarrollar grandes áreas en las matemáticas (Hipotesis de Riemman); las aplicaciones o consecuencias de esta pregunta lo observamos en la seguridad de la información (Criptografía y Teoría de Códigos)

Un ejemplo claro de lo anterior lo tenemos al revisar el algoritmo RSA

Este algoritmo fue descrito en 1977 por Ron Rivest, Adi Shamir y Len Adleman (lRSA es Rivest Shamir Adleman) en el MIT.

El encriptado RSA es un algoritmo de encriptación de llave pública (o asimétrico) por bloques, que como todos los encriptados de llave pública tiene dos llaves: una pública, que se distribuye a los usuarios que quiera el propietario de ella, y otra privada, la cual es guardada en secreto por su propietario. Así cuando se envía un mensaje, el emisor usa la llave pública del cifrado del receptor para cifrar el mensaje y una vez que dicho mensaje llega al receptor, éste se ocupa de desencriptarlo usando su llave privada.

El algoritmo sigue los siguientes pasos:

  1. Se construye un número “N”, que resulta del producto de dos primos “p” y “q”(normalmente son números muy grandes). Teniendo N = p · q y Φ(N) = (p-1) · (q-1)
  2. Se selecciona un número “e”,1 < e < Φ(N), tal que MCD (e, Φ(N)) = 1 (“e” y Φ(N) son primos relativos).
  3. Se calcula el inverso de “e”, denotado por “d”, tal que e · d = 1 (mod Φ(N))
  4. Con esto se consiguen las llaves (e, d), siendo la llave pública (e, N) y la llave privada (d, N).

Una vez tenemos las claves podemos pasar a cifrar/descfirar los mensajes:

  • Encriptar: C = Me (mod N) con MCD (M, N) = 1 y M < N
  • Desencriptar: M = Cd (mod N)

La seguridad de este algoritmo radica en que no hay maneras rápidas conocidas de factorizar un número grande en sus factores primos utilizando computadoras tradicionales.

 

Siguiendo con nuestra platica, observamos como va tomando fuerza nuestra pregunta, uno de los intentos por ver que tan frecuente son los números primos, es el encontrar una formula que genere dichos números;  hay varios intentos en la historia de las matemáticas, uno de esos intentos es la  llamada Espiral de Euler:

f(n)=n^{2}+n+41

Este polinomio es uno de mis preferidos ya que genera un comportamiento sorprendente para los primeros 100 enteros 1,2,…,100 al evaluarlos en dicha función

primos01

observamos que los números encerrados son primos, y claro también el 41 que es cuando n toma el valor de cero, veamos que pasa cuando aumentamos el valor de n a 1000

primos02

Sigue nuestro polinomio generando primos, aunque empiezan a verse mas “huecos”  en los primeros valores de 0,1,…,39 no hay ningún hueco,

Para entender este fenómeno observemos una representación geométrica:

 

2014-08-01 14.58.27

 

 

Observamos en esta espiral que al trazamos su diagonal principal tenemos los números que genera el polinomio f(n)=n^{2}+n+41

2014-08-01 14.59.36

Ahora observemos el siguiente diagrama donde los puntos negros representan a los números primos:

primos03

Lo interesante es que se observan patrones (rectas) donde se dan números primos, lo anterior podría negar que estos números aparezcan de forma aleatoria.

 

De todo lo anterior no  debe ser extraño que alguien pensara que existiera un polinomio que generara todos los números primos; ..finalmente se probo que no es así…  una lastima;  veamos una demostración de esto último.

Demostración:

Tomemos Q(x)=a_nx^n+a_{n-1} x^{n-1}+ \ldots +a_1x+a_0 un polinomio cualquiera de grado ncon coeficientes enteros, y supongamos que da valores primos para cualquier x número natural. En particular, Q(1) da como resultado un número primo p. Es decir:

Q(1)=a_n+a_{n-1}+ \ldots +a_1+a_0=p

Calculemos ahora Q(1+kp), con k un número natural cualquiera:

Q(1+kp)=a_n(1+kp)^n+a_{n-1} (1+kp)^{n-1}+ \ldots +a_1(1+kp)+a_0

Si desarrollamos todas estas expresiones (el binomio de Newton será fundamental para ello) obtenemos que todos los términos son múltiplos de p excepto, posiblemente, a_n,a_{n-1}, \ldots ,a_1 y a_0. Pero la suma de todos ellos es exactamente p (esa suma es precisamente Q(1), que hemos supuesto antes igual a p). Por tanto Q(1+kp) es un múltiplo de p, digamos mp, con m un número natural.

Ahora, hemos supuesto al comienzo que Q toma valores primos para todos los números naturales, por lo que mp debe ser un número primo. Evidentemente la única posibilidad es que m sea igual a 1, por lo que Q(1+kp)=p.

Analizando lo que hemos obtenido vemos que Q toma el valor p para todos los valores 1+kp, con k un número natural cualquiera. Es decir, Q toma el valor p para infinitos números naturales. Pero eso es imposible, ya que si eso fuera así entonces el polinomio P(x)=Q(x)-p tomaría el valor 0 en infinitos números naturales. Esto es, tendríamos un polinomio de grado n, P(x), que tiene infinitas raíces. Y eso, como sabemos, no puede suceder (un polinomio de grado n tiene, a lo sumo, n raíces reales: Teorema Fundamental del álgebra).

Por tanto, no existe ningún polinomio (no constante) con coeficientes enteros que tome valores primos para todos los números naturales

 

Saludos

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s