Dentro del marco de la computación clásica
durante varios siglos,- desde tiempos de Arquímedes-, la factorización de números enteros es un problema, para el cual aún no aún no existen métodos eficientes de resolución.
En efecto, para cifras grandes de 30 dígitos hacia arriba los ordenadores actuales requieren demasiado tiempo para procesar. Sin embargo, dentro de ámbito de la computación cuántica el problema podría reducirse, - y ciertamente se reducirá cuando sean llevados a la práctica en un computador cuántico -, mediante la aplicación de la Transformada Cuántica de Fourier, que es la herramienta fundamental del Algoritmo de Shor.
La presente
aplicación es la preparación del camino hacia la Transformada Cuántica de
Fourier, para posteriormente incorporar el capítulo dedicado al Algoritmo de
Shor, en la publicación
Conceptos Matemáticos Básicos de Computación
Cuántica.
La preparación entonces, se inicia con la
descomposición en números primos con un algoritmo sobre computación tradicional, tratando números
relativamente grandes, - dentro del ámbito de los sistemas públicos online -, de hasta 18 dígitos.
Nótese que el algoritmo desarrollado, - sustentado en el Teorema de Factorización Unica -, se puede aplicar a números enteros acotadamente más grandes. Sin embargo, el tiempo de procesamiento depende de la capacidad computacional que obviamente un usuario común y corriente no tiene. Especialmente, la demanda del procesamiento que exige la complejidad computacional para solucionar este problema.
Además, el problema de factorizar enteros en tiempo polinómico no ha sido aún resuelto en computación clásica. Hasta hoy, sólo existe el algoritmo cuántico de Peter Shor, que es capaz de encontrar factores primos de un entero en tiempo polinomial con un cierto acotado margen de error.
Ahora, estas cifras de 18 digitos transformadas a números binarios y
posteriormente llevada a vectores cuánticos, superan la sideral cifra de dos mil millones de
qubits. (Por ejemplo $n = 31 \Rightarrow m = 2^{31} = 2.147.483.648$)
+ Algoritmo Clásico
Algoritmo
x
Sistema de Descomposición Online de un Entero en sus Factores Primos
El algoritmo matemático de la aplicación desarrollada por el autor y aquí expuesta,
descompone un número Natural en sus factores primos con $n\in N \setminus n\gt2$, basado en parte por los
procedimientos clásicos de la Teoría de Números e introduciendo algunos mejoramientos propios en el algoritmo.
Comenzando por el Teorema Fundamental de la Aritmética, que postula que todo entero positivo $n > 1$ puede ser representado exactamente de una única manera como un producto de potencias de números primos:
$$n=p_1^{\alpha_1}·p_2^{\alpha_2}·p_3^{\alpha_3}\ldots · p_n^{\alpha_n}=\prod_{i=1}^n p_i^{i}$$
En otras palabras, el conjunto de lo números enteros positivos primos consecutivos, son como una "base" de todo {$n\in N\text{/}n>1$}, donde los $p_i$ son potencias de exponente {$\alpha_i\in Z \text{/}\alpha_i>=0$}. Entonces, cuando el número primo $p_i^{\alpha_i}$ en la secuencia "no cuadra", el exponente $\alpha_i$ se asume igual a cero. En efecto, un factor $p^{0} = 1$ no altera el producto que va aproximando hasta llegar a $n$.
Por ejemplo, $975=3·5^{2}·13$
Por dentro el algoritmo hizo la siguiente operación:
$$975=2^{0}·3^{1}·5^{2}·7^{0}·11^{0}·13^{1}$$
Es decir, el numero $n>1$ se expresa en función del conjunto secuencial (ordenado) de potencias de los números primos:
$\therefore\forall n\in N, n>1$ se puede expresar en función del conjunto infinito de los número primos:
$$n=2^{\alpha_1}·3^{\alpha_2}·5^{\alpha_3}·7^{\alpha_4}·11^{\alpha_5}\ldots =\prod_{p} p^{\alpha_p}$$
Luego, la búsqueda de los factores primos se realiza básicamente con el siguiente procedimiento:
Dado un número natural
mayor que 2, se divide el número por el menor de sus divisores primos y el
cociente también se divide por el menor de sus divisores primos.
Así sucesivamente con los demás cocientes, a fin de culminar con un último
cociente primo en ciclo. En otros términos, un número que se divide por sí mismo
y arroja como cociente 1.
Ilustremos un factorización sobre un número de 18 digitos, realizada con la aplicación del algoritmo usando nuestro software:
$$856779863713918828=2^{7}·3^{2}·11·67612047325909$$
Nótese que no existe ninguna otra factorización de 856779863713918828 en términos de números primos, donde el orden de los factores es irrelevante en un producto.
+ Uso de la Aplicación
Uso de la Aplicación
x
Sistema de Descomposición Online de un Entero en sus Factores Primos
1 Se ingresa un número en el campo editor, mayor que 2 y de hasta 18 dígitos.
2
Se presiona el botón Factorizar.
3 Si se desea obtener una numero aleatorio, basta con presionar el ícono Aleatorio, adyacente al campo editor e insertará un número de 18 cifras.
Ingreso Número y Ejecución del Algoritmo
Cuando se presiona el botón Factorizar, se ejecuta la variante del Algoritmo DocIRS, de donde se entregará el resultado
que se muestra en la vista de más abajo. Los factores primos del número
ingresado se despliegan con marcos rojos, acompañado de una serie de otros datos
que se generan en torno a al proceso de cálculo.
Vista de Resultados del Algoritmo
Dentro de las serie de datos que se visualizan, pueden aparecer los íconos o en el reglón Verificación Producto Factores Primos. El primer ícono significa que se muestra el cálculo en forma precisa y el segundo ícono implica que el computador lo presenta como una aproximación de las cifras.
Presionando cualquiera de estos dos íconos, se desplegará un mensaje con la verificación de los cálculos. Por un lado el logaritmo natural directo sobre el producto de los factores primos y por otro la suma de los logaritmos de los factores comparados con el logaritmo natural del número ingresado.
Nótese que se transforma el número ingresado a binario,
de modo de ir preparando la
aplicación hacia la Transformada Cuántica de Fourier y posteriormente mostrar un
ejemplo de 3 o cuatro qubits en un circuito cuántico.
En el siguiente bloque se despliega una tabla que va almacenando dinámicamente, - sólo durante la sesión-, el número
ingresado y los correspondientes factores primos que lo componen.
Selección Aleatoria
o 
en el reglón Verificación Producto Factores Primos. El primer ícono significa que se muestra el cálculo en forma precisa y el segundo ícono implica que el computador lo presenta como una aproximación de las cifras.
