Factorización de enteiros

miniatura| Descomposición do número 864 en factores primos

En matemáticas e máis precisamente en aritmética, a **descomposición en produto de factores primos**, tamén coñecida como **factorización de enteiros** ou **descomposición en factores primos**, consiste en  escribir un número natural distinto de cero na forma dun produto de números primos. Por exemplo, se o número dado é 45, a factorización en primos é 45 = 3^2 \cdot 5 = 3 \cdot 3 \cdot 5  .

Por definición, un número primo en si non se pode descompoñer no produto de varios números primos. 

\begin{align}
&5 = 5. \\
&25 = 5 \cdot 5 = 5^2. \\
&125 =5 \cdot 5 \cdot 5 = 5^3. \\
&360 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 3 \cdot 5 = 2^3 \cdot 3^2 \cdot 5.\\
&861 = 3 \cdot 7 \cdot 41.\\
&1001 =  7 \cdot 11 \cdot 13.\\
&1010021 =  17 \cdot 19 \cdot 53 \cdot 59.\\
\end{align}

A factorización é sempre única, de acordo co teorema fundamental da aritmética. Escribir números enteiros como produtos de factores primos facilita o seu manexo en problemas de divisibilidade, fracción ou raíz cadrada.

## Descomposición en produto de números primos 
O teorema fundamental da aritmética permítenos afirmar que calquera enteiro estritamente positivo ten unha única descomposición en factores primos.

Para calquera enteiro natural  maior ou igual a 1, existe unha secuencia finita única  tal que:

# os  son números primos tal que, se , entón ;
# os  son enteiros naturais distintos de cero;
#  é o produto dos números .

## Usos básicos 
Escribir un número enteiro como produto de factores primos simplifica o traballo sobre produtos, múltiplos e divisores. 

### Múltiplos e divisores 
Asumimos que se escribe a descomposición de  en produto de factores primos
:n=\prod_{i=1}^rp_i^{k_i}.
O número enteiro  é múltiplo de  se e só se a descomposición de  nun produto de factores primos contén polo menos cada  elevado a unha potencia  maior ou igual a .

O enteiro  é un divisor de  se e só se existen  enteiros  que satisfán  tal que 
:d=\prod_{i=1}^rp_i^{k'_i}.

Nesta forma, entón é posíbel facer unha lista de todos os divisores de  e determinar o seu número:

Polo tanto, os divisores de 45 son: 
:3^0 5^0,~3^1 5^0,~3^2 5^0,~3^0 5^1,~3^1 5^1,~3^2 5^1, 
é dicir, 6 divisores. 

A suma dos divisores positivos de  vén dada pola fórmula 
:\sigma(n)=\prod_{i=1}^r\frac{p_i^{k_i + 1}-1}{p_i-1}

### MCD e MCM 
O MCD (máximo común divisor) de dous números enteiros  e  maiores ou iguais a 2 calcúlase mediante o produto dos factores primos que aparecen tanto na descomposición de  *como de*  provistos do *menor* dos expoñentes atopados na descomposición de  e . Entón, 
:{\rm se}\quad a = 2^3\times 3^4\times 5^2\times 7\quad{\rm e}\quad b=2^2\times 3^5\times 7^3\times 11\quad{\rm daquela}\quad{\rm mcd}(a,b) = 2^2\times 3^4\times 7.

O MCM (mínimo común múltiplo) de dous números enteiros  e  maiores ou iguais a 2 calcúlase como o produto dos factores primos que aparecen en  *ou* en  provistos do *maior* dos expoñentes atopados na descomposición de  e de . Entón, 
:{\rm se}\quad a = 2^3\times 3^4\times 5^2\times 7\quad{\rm e}\quad b=2^2\times 3^5\times 7^3\times 11\quad{\rm daquela}\quad{\rm mcm}(a,b) = 2^3\times 3^5\times 5^2\times 7^3\times 11.

### Formas reducidas 
A descomposición en factores primos pode ser útil para reducir unha fracción a unha fracción irredutíbel, para descompoñela en elementos simples, para reducir dúas fraccións ao mesmo denominador ou para reducir expresións que conteñan raíces cadradas ou raíces -ésimas.

#### Fraccións irredutíbeis 
Para reducir unha fracción a forma irredutíbel, débese simplificar o numerador e o denominador da fracción polo MCD destes dous números. Escribir os números como produtos de factores primos fai que a simplificación sexa máis obvia: 
:\frac{1827}{1050}=\frac{3^2\times 7\times 29}{2\times 3\times 5^2\times 7}  \frac{3\times 29}{2\times 5^2}=\frac{87}{50}

#### Fraccións  co mesmo denominador 
Para escribir dúas fraccións co mesmo denominador, podemos escoller como común denominador o MCM dos dous denominadores. Tamén aquí pode resultar útil a descomposición en produtos de factores primos: 
:\frac{5}{28}+\frac{3}{70}=\frac{5}{2^2\times 7}+ \frac{3}{2\times 5\times 7}  \frac{5\times \color{Red} 5}{2^2 \times 7\times \color{Red}{5}}+ \frac{3\times \color{Red}2}{2\times 5\times 7\times \color{Red}2}  \dfrac {31}{2^2\times 5\times 7}=\dfrac{31}{140}

#### Redución de raíces 
Calquera número enteiro maior ou igual a 2 é un cadrado se todos os expoñentes da súa descomposición no produto dos factores primos son pares. Calquera número enteiro maior ou igual a dous descomponse no produto dun cadrado e un número cuxa descomposición en produtos de factores primos só contén expoñentes iguais a 1. Nesta forma, é posíbel escribir unha raíz cadrada en forma irredutíbel: 
:\sqrt{4752}=\sqrt{2^4\times 3^3\times 11}=\sqrt{(2^2\times 3)^2\times 3\times 11}=12\sqrt{33} .

Esta propiedade xeneralízase ás raíces -ésimas.

## Algoritmos de factorización 
A procura de algoritmos eficientes é  un obxectivo da teoría de números.

### Algoritmo inxenuo 
A primeira idea é escanear a lista de números primos probando se o número primo  divide . Se un primo si o divide, comezamos de novo o algoritmo para , probando só os divisores primos que aínda son posíbeis. Detémonos cando o número primo a probar é maior que a raíz cadrada do número que se supón que debe dividir.

Entón, para descompoñer 2088 en produto de factores primos

Obtemos a descomposición esperada: 2088=2^3 \cdot 3^2 \cdot 29.

### Estado actual da arte 
Se un número grande de  bits é o produto de dous números primos que probabelmente teñan o mesmo tamaño, entón non se coñece ningún algoritmo que poida factorizar en tempo polinómico. O que significa que non hai un algoritmo coñecido que poida factorizar nunha orde de tempo O(*nk*) calquera que sexa a constante . Porén, hai algoritmos que son tan rápidos como Θ(e*n*) (orde asintótica). Noutras palabras, os algoritmos máis coñecidos son subexponenciais, pero superpolinomiais. En particular, o algoritmo máis coñecido é a creba xeral do corpo de números  (GNFS polas súas siglas en inglés).

### Obxectivo especial 
O tempo de execución dos algoritmos de factorización de propósitos especiais depende das propiedades dos seus factores descoñecidos: tamaño, forma especial, etc. Exactamente, o tempo de execución depende do que varía entre os algoritmos.

* Divisións sucesivas
* Algoritmo rho de Pollard
* Algoritmo p-1 de Pollard
* Factorización de curva elíptica de Lenstra
* Congruencia de cadrados (Método de factorización de Fermat)
* Creba especial de corpo de números (SNFS)

### Obxectivo  xeral 
O tempo de execución dos algoritmos de factorización de propósito xeral depende só do tamaño do número enteiro que se vai factorizar. Este é o tipo de algoritmo usado para factorizar os números RSA. A maioría dos algoritmos de factorización de propósito xeral baséanse no método da congruencia de cadrados.

* Creba cadrática
* Creba xeral do corpo de números (GNFS)

## Notas 
## Véxase tamén 
### Bibliografía 
*  Chapter 5: Exponential Factoring Algorithms, pp.&nbsp;191–226. Chapter 6: Subexponential Factoring Algorithms, pp.&nbsp;227–284. Section 7.4: Elliptic curve method, pp.&nbsp;301–313.
* Donald Knuth. *The Art of Computer Programming*, Volume 2: *Seminumerical Algorithms*, Third Edition. Addison-Wesley, 1997. . Section 4.5.4: Factoring into Primes, pp.&nbsp;379–417.
* .
* 

### Outros artigos 
* Factorización
* Número p-ádico
* Algoritmo_de_Shor

### Ligazóns externas 
* Prime factorization Cuemath.
* Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P." Annals of Mathematics 160(2): 781–793 (2004). August 2005 version PDF
* Dario Alpern Calculadora online para factorizar enteiros grandes