Descomposición factorial en números primos

Posted on lunes, junio 24, 2013 by Pedro Wave

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.

diarrea mental.
1. f. coloq. empanada mental.

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:

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: \mathbb{P}

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:

Descomposición en la nube de SkyDrive

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 SkyDrive, 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.



Descarga plantilla compatible con Excel 2003

Baja la 4ª versión de SkyDrive. 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 (Sites Google) o desde el enlace (Microsoft OneDrive)


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:

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:
Número primo Longitud Tiempo de proceso
535006138814359 15 00:00:18
4847464544434241 16 00:00:54
55350776431903243 17 00:03:03
496481100121144169 18 00:09:12
6082394749206781697 19 00:32:19

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:
"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."

2 Response to "Descomposición factorial en números primos"

.
gravatar
Victor Arteaga Says....

Holas...

◘ Interesante el desarrollo de su algoritmo de primalidad; pero sin desmerecer su eficiencia y rendimiento, pase los numeros de su ejemplo por un algoritmo basico en desarrollo y estos son mis tiempos:

Número primo Longitud Tiempo de proceso
535006138814359 15 00:00:09
4847464544434241 16 00:00:26
55350776431903243 17 00:01:29
496481100121144169 18 00:04:45

◘ Respecto al proceso de ir mejorando las formulas, como explica en otra pagina, la solucion al problema de solo tomar numeros que terminan en 1, 3, 7 y 9, no es correcto, ya que con esto solo discrimina multiplos de 2 y 5, donde los multiplos de 3 son mucho mas que los de 5.
○ Aplicando la serie progresiva (+2)(+4) tendria multiplos de 5 y algunos cuantos de 3.
• Esta serie es facil de implementar, donde partiendo de 5 se le suma +2 = 7 y se tiene un grupo o par de numeros de base para testear (5, 7)
• Luego suma al ultimo obtenido +4 para obtener el primero de grupo y luego sumar +2 y asi conseguir otro grupo o par.
7 + 4 = 11 + 2 = 13 (11, 13)
13 + 4 = 17 + 2 = 19 (17, 19) y asi sucesivamente.
• Otra forma seria determinar los primeros de cada grupo sumando (+6) y luego a cada uno se le suma +2 para completar el grupo par.

◘ En mi proyecto genero numeros base de manera directa y simple, donde automaticamente estan excluidos los multiplos de los primos que en su algoritmo inicialmente revisa, donde cada If-Then consume memoria y aumenta el tiempo de procesamiento. La generacion de los numeros base a considerar a ser primos, se reduce casi a 1/4 parte del rango de busqueda, esto gracias a mi descubrimiento de los "Primos Origen", ya que encontre que todos los primos se originan de unos cuantos numeros especiales a los que llamo primos origen.
La nueva concepcion de la organizacion de los numeros primos, es clara y precisa, donde nada esta al azar como se cree o creia, lo cual me ha facilitado desarrollar algoritmos de tamis, de primalidad y de factorizacion de enteros de mas de 24 digitos en tan solo unos minutos.

○ La limitacion en Excel como bien lo expone, es la precision de los calculos, que es confiable hasta 15 digitos; pero reduciendo el numero a menos digitos, es posible evaluar sin problema hasta 18 digitos, ya que todo es proporcional con los primos origen y aciendo arreglos similares, se determina en Excel hasta numeros con 24 digitos.

◘ Para numeros con mas digitos, maneje como cadenas de texto, donde implementando funciones, pueda realizar las operaciones necesarias, donde todo dependera de su metodo para que la complejidad no se incremente como asi tambien el tiempo de procesamiento. En mi caso solo realizo operaciones aritmeticas basicas para largas cadenas de digitos y determinar la primalidad de numeros grandes.

Bueno, espero le sea de utilidad mis sugerencias y comentarios.

.
gravatar
Pedro Wave Says....

El carácter ? ayuda a obtener el siguiente número primo de la descomposición factorial. ¿Pero ya sabes que carácter se debe escribir en la celda C11 para calcular automáticamente los factores primos del número escrito en B11?

Si aún no lo sabes, te lo digo. Es el carácter ¶ o signo tipográfico Calderón que no tiene nada que ver con el estadio Vicente Calderón y el trágico suceso del domingo pasado entre ultras del Atlético de Madrid y del Deportivo de La Coruña.

En Excel no se usa tanto pero en Word y otros editores sirve para Mostrar todo, como saltos de página, marcas de párrafo y otros símbolos de formato ocultos, y por eso lo he usado para mostrar todos los números primos de la descomposición factorial introduciendo un único carácter en la celda C11.

El símbolo ¶ se visualiza con las teclas Alt + 20 (en Windows) y Option + 7 (en Mac).

El reto lo ganó mi amigo Verzulsan hace más de un año, en el foro de Ayuda Excel: Calcular factores primos. Ahora si que está completo este artículo!!!

Leave A Reply

Dime si te gusta lo que lees y, si no te gusta, dime por qué. Tengo habilitada la moderación de comentarios. Tu comentario se publicará pronto.

Tell me if you like what you read here and if you don't like, tell me why. I've enabled comment moderation. Your comment will be published ASAP.

Mi Lista de Blogs- My Blog List