Factorización de los enteros

factorización de los enteros - Wikilingue - Encydia

En matemáticas y más precisamente en teoría de números, la factorización de los enteros es el proceso de encontrar un divisor no trivial (diferente del 1 y del mismo número) de un número compuesto. Si se tiene un algoritmo por factoritzar cualquier entero entonces el mismo algoritmo sirve por factoritzar-lo en factores primeros en base de aplicar el mismo algoritmo repetidamente hasta que todos los factores sean números primos, esta factorización se conoce como descomposición en producto de factores primeros o factorización en números primos y es el proceso de resolución del problema siguiente: sea un entero estrictamente positivo, cóm escribirlo en forma de un producto de números primos; por ejemplo, si el número dado es 45, la factorización en números primos es 3²·5..

Por definición, un número primo no se puede descomponer. También se puede decir que es el resultado de su propia descomposición. Ejemplos:

11 = 11

25 = 5 × 5 = 5²

125 = 5 × 5 × 5 = 5³

360 = 2 × 2 × 2 × 3 × 3 × 5 = 2³ × 3² × 5

1.001 = 7 × 11 × 13

1.010.021 = 17 × 19 × 53 × 59

La factorización es siempre única, de acuerdo con el teorema fundamental de la aritmética. Este problema es de una importancia considerable en matemáticas, en criptografía, en teoría de la complejidad, y para los ordenadores cuánticos.

Mesa de contenidos

1 Descomposición en números primos
2 Aplicaciones prácticas
- 2.1 Dificultad y Complejidad
3 Algoritmos de factorización
4 Artículos relacionados
5 Enlaces externos
6 Referencias

Descomposición en números primos

Todo número natural n no nulo se puede escribir de manera única como el producto fenecido de números primos elevados a una potencia adecuada.

$\forall n\in\mathbb{N}^*, \exists! (\alpha_p)_{p\in\mathcal{P}}\in\mathbb{N}^{(\mathcal{P})}: n = \prod_{p\in\mathcal{P}} p^{\alpha_p}$ .

La lista completa de los divisores de un número puede ser deducida de la descomposición en factores primeros incrementando los exponentes de cero hasta el número buscado. Por ejemplo, como que 45= 3²·5, 45 entonces es divisible entre 3⁰·5⁰, 3⁰·5¹, 3¹·5⁰, 3¹·5¹, 3²·5⁰, y 3²·5¹, es decir sus divisores son 1, 5, 3, 15, 9, y 45. En cambio la descomposición en factores primeros incluye sólo los factores primeros.

Aplicaciones prácticas

Sean dos números primos grandes dados, es fácil obtener el producto. En cambio, es mucho más difícil encontrar los factores primeros de este producto. Es el que se llama una función unidireccional. Esto se aplica en los sistemas modernos en criptografía. La base está en qué lo xifratge se hace conociendo el producto pero para hacer el desxifratge hay que conocer la factorización. Si se encontrara un método rápido para resolver el problema de la factorización de los números enteros, entonces se podrían romper varios sistemas criptográficos importantes, incluyendo el algoritmo de clave pública RSA y el generador de números pseudoaleatoris Blum Blum Shub. La puesta a punto de un ordenador cuántico es uno de estos métodos.

Aunque la factorización sea una manera de romper estos sistemas, pueden existir otros que no impliquen la factorización. Así, es posible que el problema de la factorización entera sea verdaderamente difícil, pero que estos sistemas puedan ser rotos rápidamente. Una excepción rara es el generador Blum Blum Shub. Se ha demostrado que es exactamente igual de difícil como la descomposición en producto de factores: si se puede romper el generador en tiempo polinómico entonces, se puede factoritzar los enteros en tiempo polinómico, y viceversa.

Dificultad y Complejidad

Si un número de n bits es el producto de dos números primos que son probablemente de medida similar, entonces actualmente no hay ningún algoritmo publicado para poder factoritzar-lo en tiempo polinómico. El que quiere decir esta afirmación es que no existe ningún algoritmo publicado que pueda factoritzar-lo en tiempo O(n^k) independientemente de qué sea la constante k. Existe algoritmos, sin embargo, que son más rápidos que (eⁿ). En Otras Palabras, los mejores algoritmos publicados son subexponencials, pero superpolinomics. En particular, el mejor algoritmo publicado que cumpla en tiempo asintótico es la criba general del cuerpo de números (GNFS), su complejidad es:

$O\left(\exp\left(\left(\begin{matrix}\frac{64}{9}\end{matrix} b\right)^{1\over3} (\log b)^{2\over3}\right)\right)$

Al analizar las clases de complejidad del problema de la factorización de los enteros, hay que distinguir dos versiones del problema ligeramente diferentes:

La versión problema función: dado un entero N, encontrar un entero d con 1 < d < N que sea divisor de N (o concluir que N es primero si no hay ningún). Este problema es evidentemente FNP y no se sabe si tiene complejidad FP o no. Esta es la versión del problema que resuelven la mayoría de las implementaciones prácticas.
La versión problema decisión: dado un entero N y un entero M con 1 ≤ M ≤ N, tiene N un factor d con 1 < d < M? Esta versión es útil porque las clases de complejidad que han sido más estudiadas son clases de problemas decisión, no de problemas función. Esta versión del problema en forma de decisión es una elección natural porque se puede combinar con una busca binaria para resolver la versión función del problema en una cantidad logarítmica que decisiones.

No se sabe exactamente qué clases de complejidad contiene el problema de factorización de enteros. Se sabe que su forma de decisión-problema (" Tiene N un factor menor que M? ") tiene complejidad NP y co-NP. Esto es porque tanto la respuesta Si como la respuesta No se pueden comprobar si se tienen los factores primeros con sus certificados de primalitat. Se sabe que es de clase BQP gracias al algoritmo de Shor. Se sospecha que se encuentra fuera de las tres clases de complejidad (P, NP Completo, co-NP Completo). Si fuera posible probar que es de cualquier de estas dos últimas, esto implicaría que NP = co-NP. Este sería un resultado muy sorpresivo, y por eso se sospecha que la factorización de enteros se encuentra fuera de ambas. Mucha gente ha intentado encontrar algoritmos clásicos de tiempo polinómico, y ha fallado; por eso se sospecha que se encuentra fuera de P.

Curiosamente, un problema de decisión diferente pero relacionado, el problema: " es N un número compuesto? " (o el que es el mateixl: " es N un número primo? ") parece ser mucho más sencillo que el problema de encontrar los factores en los cuales se descompone N. En concreto, puede ser resuelto en tiempo polinómico. Ved test de primalitat

Algoritmos de factorización

De propósito general

El tiempo de ejecución de un algoritmo de factorización de propósito general depende sólo de la medida del entero a factoritzar. Este es el tipo de algoritmo que se usa por factoritzar números RSA. La mayoría de algoritmos de factorización de propósito general están basados en el método de congruencia de cuadrados. A continuación se listan algunos de los algoritmos de propósito general más conocidos:

Algoritmo de Dixon
Factorizació con fracciones continuas
Criba cuadrática
Algoritmo general de criba de cuerpo de números
Factorizació de formas cuadradas de Shanks

De propósito específico

El tiempo de ejecución de un algoritmo de factorización de propósito específico depende de las propiedades de sus factores desconocidos: medida, forma especial, etc. Dichos factores cambian de un algoritmo al otro.

Factorización por prueba de divisiones
Algoritmo rho de Pollard
Algoritmo p-1 de Pollard
Algoritmo p+1 de Williams
Factorización de curva elíptica de Lenstra
Método de factorización de Fermat
Algoritmo especial de criba de cuerpo de números

Otros algoritmos

Artículo principal: ordenador cuántico

Factorización de los enteros

Factorización de los enteros