Factorizacion

Republica Bolivariana De Venezuela

Ministerio Del Poder Popular Para La Defensa

Universidad Nacional Experimental Politécnica De La Fuerza Armada Nacional

CINU_ISD_01

Asignatura: Matemáticas

FACTORIZACIÓN

Prof: Alumno:

Pastor Maldonado Cristian Moreno

C.I. 22.500.154

Fecha: Noviembre Del 2012

Factorización

En matemáticas, la factorización (o factoreo) es la descomposición de una expresión matemática (que puede ser un número, una suma, una matriz, un polinomio, etc) en forma de multiplicación. Existen diferentes técnicas de factorización, dependiendo de los objetos matemáticos estudiados; el objetivo es simplificar una expresión o reescribirla en términos de «bloques fundamentales», que reciben el nombre de factores, como por ejemplo un número en números primos, o un polinomio en polinomios irreducibles.

El teorema fundamental de la aritmética cubre la factorización de números enteros, y para la factorización de polinomios, el teorema fundamental del álgebra. La factorización de números enteros muy grandes en producto de factores primos requiere de algoritmos sofisticados, el nivel de complejidad de tales algoritmos está a la base de la fiabilidad de algunos sistemas de criptografía asimétrica como el RSA.

Factorización de enteros

En teoría de números, la factorización de golfas o factorización de primos consiste en descomponer un número compuesto (no primo) en divisores no triviales, que cuando se multiplican dan el número original.

Cuando los números son muy grandes no se conoce ningún algoritmo que resuelva eficientemente este problema; un reciente intento de factorizar un número de 200 dígitos (RSA-200) tardó 18 meses y consumió más de medio siglo de tiempo de cálculo. Su supuesta dificultad es el núcleo de ciertos algoritmos criptográficos, como el RSA. Muchas áreas de las matemáticas y de las ciencias de la computación, como la teoría algebraica de números, las curvas elípticas o la computación cuántica, están relacionadas con este problema.

Descomponer dos números de igualesta longitud no tiene por qué tener la misma complicación. Actualmente (2006) se considera que los casos más duros son aquellos para los que los factores son dos números primos, elegidos al azar, de aproximadamente el mismo tamaño.

Descomposición en factores primos

Por el teorema fundamental de la aritmética, cada entero positivo tiene una única descomposición en números primos. La mayor parte de los algoritmos de factorización elementales son de propósito general, es decir, permiten descomponer cualquier número introducido, y solo se diferencian sustancialmente en el tiempo de ejecución.

Aplicaciones prácticas

La dureza de este problema, se encuentra en el núcleo de varios sistemas criptográficos importantes. Un algoritmo veloz para la factorización de enteros significaría que el algoritmo de clave pública RSA es inseguro. Algunos sistemas criptográficos, como el algoritmo de clave pública Rabin y el generador de números pseudoaleatorios Blum Blum Shub garantizarían una mejora en su seguridad; cualquier método que logre quebrarlos puede ser utilizado para crear un algoritmo de factorización más veloz; si la factorización de enteros es veloz, éstos se vuelven más duros. En contraste, pueden existir ataques más eficientes al problema RSA, pero no se conoce ninguno.

Un problema duro similar con aplicaciones criptográficas es el problema del logaritmo discreto.

Estado actual

Un equipo en la Agencia Federal Alemana para Seguridad de Tecnología de Información (BSI) sostiene el récord por factorización de semiprimos en la serie propuesta por la Competición de factorización RSA, con patrocinio de RSA Security. El 9 de mayo de 2005, este equipo anunció la factorización de RSA-200, un número de 663 bits, usando la criba general del cuerpo de números.

El mismo equipo más tarde anunció la factorización de RSA-640, un número más pequeño, conteniendo 193 digitos decimales (640 bits) el 4 de noviembre de 2005.

Ambas factorizaciones requirieron varios meses de tiempo de computadoras, utilizando el poder combinado de 80 CPUs Opteron AMD.

Dificultad y complejidad

Si un número grande, de b bits es el producto de dos primos de aproximadamente el mismo tamaño, no existe algoritmo conocido capaz de factorizarlo en tiempo polinomial. Esto significa que ningún algoritmo conocido puede factorizarlo en tiempo O(bk), para cualquier constante k. Aunque, existen algoritmos que son más rápidos que O(ab) para cualquier a mayor que 1. En otras palabras, los mejores algoritmos son súper-polinomiales, pero sub-exponenciales. En particular, el mejor tiempo asintótico de ejecución es el del algoritmo de criba general del cuerpo de números (CGCN), que para un número n es:

Para una computadora ordinaria, la CGCN es el mejor algoritmo conocido para números grandes. Para una computadora cuántica, en cambio, Peter Shor descubrió en 1994 un algoritmo que lo resuelve en tiempo polinómico. Esto tendría implicaciones importantes en la criptografía, si alguna vez se construyese una computadora cuántica. El algoritmo de Shor sólo tarda un tiempo O((log n)3) y ocupa un espacio O(log n). En 2001, la primera computadora cuántica de 7 cubits fue la primera en correr el algoritmo de Shor. Factorizó el número 15.

No se conoce exactamente cuales clases de complejidad contienen 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 respuestas SI y NO pueden ser comprobadas si se proveen los factores primos junto a sus certificados de primalidad. Se conoce que está en 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 fuese posible probar que se encuentra en cualquiera de estas dos últimas, eso implicaría que NP = co-NP. Ese sería un resultado muy sorprendente, y por ello se sospecha ampliamente que la factorización de enteros se encuentra fuera de ambas. Mucha gente ha intentado encontrar algoritmos clásicos de tiempo polinomial para esta, y ha fallado; por esto se sospecha que se encuentra fuera de P. Otro problema en NP pero que no

...