#ExcelPedroWave

Problemas de descomposición

Ahora que estamos en época de exámenes, ¿a quién no le ha surgido una descomposición factorial o metabólica?, pues las dos acepciones se encuentran en el Diccionario de la Lengua Española:

descomposición.

1. f. Acción y efecto de descomponer o descomponerse.

2. f. coloq. diarrea.

No vamos a hablar de la diarrea mental o de la empanada mental que surge cuando nos hemos empapuzado de tantos temas, del examen o de la oposición, que no los podemos digerir ni descomponer para responder a las preguntas del examen, sino de una descomposición mental y matemática.

Si alguien cree que la factorización de enteros se resuelve con una fórmula simple está muy equivocado.  Los algoritmos que tratan de descomponer un número en sus factores primos son una buena baza para poner a trabajar a los ordenadores cuánticos, los más potentes diseñados hasta el momento. Uno de los algoritmos más conocidos es el Algoritmo de Shor.

Problema RSA

El día que el algoritmo de Shor funcione en una computadora cuántica no servirán de nada los códigos secretos que usamos para hacer una transacción electrónica o firmar un documento con nuestro DNI electrónico.  Todas las claves públicas RSA será posible descifrarlas, es el conocido como el Problema RSA en criptografía que confía en la seguridad de no poder hallar los dos números primos que descomponen una clave secreta en tiempo polinómico de computación.

Me surge una duda, las agencias de inteligencia norteamericana ¿ya tienen ordenadores cuánticos capaces de descifrar claves secretas, descomponiendo factorialmente la clave en sus dos números primos?  Si es así, nuestra privacidad está por los suelos y también nuestra confianza en la seguridad de nuestros datos y nuestras comunicaciones privadas.  El programa de vigilancia PRISM puede haber acabado con ellos, según informan en los siguiente enlaces de actualidad:

PRISM (programa de vigilancia)

Project Chess - las escuchas en Skype son una realidad

Por qué la privacidad es necesaria: desmontando el "no tengo nada que ocultar"

Lo que está en juego es que ni siquiera seremos autores de nuestros propios artículos si cualquiera puede suplantarnos usando nuestras claves secretas o creándolas en lugar nuestro (por si creen que sin usar Internet estarán libres de la suplantación de su identidad digital).

Descomposición factorial

En este artículo no trataremos de romper claves compuestas por números primos extremadamente largos, sino de 6 cifras o hasta 1.000.000, con una plantilla que sirva en la escuela o el instituto y que pueda ser subida a la nube para poder ejercitarnos en la búsqueda de los factores primos en cualquier lugar con conexión a Internet.

La descomposición factorial permite obtener los números primos con sus potencia, que son divisores de un número entero.  Por ejemplo:

70776 = 2³ · 3² · 983

Se acuerda usar el símbolo de puntuación "·" como operador de multiplicación de una factorización de números primos, aunque se pueden usar otros símbolos, como: . (punto decimal), x (signo por), * (signo asterisco).

A la derecha está la descomposición factorial del entero 70776, como producto de los factores primos: 2, 3 y 983.  El número 2 está elevado a la 3ª potencia, pues es necesario multiplicarlo tres veces:

2³ =2 x 2 x 2 = 8.

Números primos

En el ejemplo anterior es fácil obtener los factores 2 y 3 pues son números pequeños, pero no es tan fácil saber si 983 es primo.

Los números primos son números naturales (enteros mayores que 1) que son divisibles por 1 y por sí mismos, y hay infinitos. El conjunto de todos los números primos se representa con el símbolo: 

Uno de los métodos para averiguar si un número compuesto es primo es probar a dividirlo por cada uno de los números primos menores que él y si no hay ninguno que lo divida se puede asegurar que es primo.

Hay números primos especiales como los que comenta la novela La soledad de los números primos, son los números primos gemelos, que son dos números primos impares seguidos (excepto el 2, todos los números primos son impares) como el 11 y el 13, el 17 y el 19, o el 41 y el 43.

En los siguientes enlaces se pueden estudiar algunos de los problemas conocidos con números primos, que tantos quebraderos de cabeza dan a los estudiosos de la teoría de números:

Conjetura de los números primos gemelos

Conjetura de Goldbach (uno de los problemas no resueltos más difíciles de la teoría de números)

Teorema de los números primos

Hipótesis de Riemann

Problemas del milenio (el que los resuelva ganará un millón de dólares)

Descomposición en la nube

A raíz de una consulta de un profesor de matemáticas, AyudaExcel.com - Fórmula o macro para expresar una factorización prima en potencias, se me ocurrió realizar esta plantilla en Excel 2010, que permite practicar la descomposición factorial de un número compuesto en sus factores primos desde OneDrive, sin necesidad de tener instalado Excel, gracias a resolverlo solamente con fórmulas, pues las macros no se pueden subir a la nube de Microsoft en Excel 2007 o 2010.

NOTA: En esta hoja se puede editar la celda B11 y el rango C11:C30, ¡no modifiques otras celdas!

AVISO: Para borrar los números, si no funciona la tecla de retroceso o Supr, escribe un espacio en blanco y la tecla de retroceso para dejar la celda vacía.

Para ajustar el zoom en la nube:

• En el móvil o celular usa dos dedos en la pantalla, como haces para ampliar o reducir una foto.
• En el PC sitúa el cursor dentro del buscador y presiona la tecla <Control> girando la ruleta del ratón.

Descarga la plantilla

Baja la 5ª versión de esta descomposición. Admite números entre 2 y 2.251.799.999.999
La versión en la nube ExcelWebApp solamente admite hasta 1.000.000
La ayuda con ? no funciona en Excel 2003 para valores muy grandes.

PARA DESCIFRADORES:
Un carácter oculto, escrito en la celda C11, calcula automáticamente los factores primos del número escrito en B11.  
¿Eres capaz de adivinarlo?

Descarga el fichero desde el icono (Google Drive) o desde el enlace (Microsoft OneDrive)

DescomposiciónFactorial-PW5.zip 

Hoja Factores

• Celda B11 - Introducir el número compuesto a descomponer factorialmente (entre 2 y 1000000).
• Rango C11:C30 - Introducir los factores primos que descomponen factorialmente el número anterior. (avisa si no es primo o si no divide el número compuesto)
• Celda B8 - Se visualiza la descomposición factorial como potencias de números primos. (ejemplo 234 = 2 · 3² · 13)
• Celda F10 - Para cambiar el símbolo multiplicador de los factores primos , por defecto "·" (ejemplo:  ·  x  .  *).

Hoja Primos

• Rango A2:A21 - Fórmula para averiguar si es un número primo si es mayor que 0.
• Rango B2:B21 - Lista los números primos en orden creciente.
• Rango C2:C21 - Calcula el número de repeticiones de cada número primo.
• Rango D2:D21 - Obtiene la descomposición factorial.
• Rango G2:H21 - Lista auxiliar de los superíndices para representar gráficamente las potencias de los números primos (hasta la 20).

Hoja Divisores

• Rango A2:A21 - Con los números compuestos de Factores!B11:B21
• Rango B2:B21 - Fórmula matricial para obtener los factores primos.
• Rango C2:C21 - Divisores de los números compuestso y sus factores.
• Rango D2:D21 - Número primo, factor primo ó menor que F1.
• Celda F1 - Para que el usuario averigüe los divisores menores que este valor, por defecto: 20.

Fórmula matricial para obtener los factores primos:

Gracias a esta fórmula, al introducir el signo "?" sin las comillas en el rango Factores!C11:C30, se puede conocer cuál es el factor primo.

Fórmulas para identificar números primos

La fórmula para averiguar si un número es primo la he sacado del gran experto en Excel, José Ramón García, en su página web:

www.jrgc.es - AVERIGUAR SI UN NÚMERO ES PRIMO USANDO UNA FÓRMULA

La siguiente fórmula matricial (introducida pulsando a la vez las teclas: Ctrl + Mayús + Entrar) permite saber si un número es primo (resultado mayor que 0), hasta el 4.295.098.367 en Excel 2003 y hasta el 1.099.513.724.928 en las versiones posteriores, suficiente para valores de 1000 (raíz cuadrada de 1.000.000 que es el número compuesto máximo de esta plantilla).

Con la 4ª fórmula del enlace anterior se puede averiguar si un número de 15 cifras es primo (máxima precisión de Excel). Con macros en VBA se puede resolver para más dígitos con un tiempo de computación mayor con una función como ésta:

www.jrgc.es - Función para saber si un número es primo

Pero esto lo dejo para próximos artículos sobre cálculos con grandes números, de momento si nos fiamos de Edward Snowden en cuanto a la protección que ofrece la encriptación:

theguardian - Edward Snowden's live Q&A: eight things we learned

"La encriptación funciona. Los sistemas de cifrado fuertes correctamente implementados son una de las pocas cosas en las que usted puede confiar. Desafortunadamente, la seguridad extrema es tan terriblemente débil que la NSA puede encontrar con frecuencia maneras de saltársela."