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 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):
DescomposiciónFactorial-PW5.xlsx
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."