Factorización de enteiros

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 sí non se pode descompoñer no produto de varios números primos.

$\begin{array}{cc}& 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{array}$

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 Modelo:Mvar maior ou igual a 1, existe unha secuencia finita única Modelo:Math tal que:

1. os Modelo:Mvar son números primos tal que, se Modelo:Math, entón Modelo:Math;
2. os Modelo:Mvar son enteiros naturais distintos de cero;
3. Modelo:Mvar é o produto dos números Modelo:Mvar.

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 Modelo:Mvar en produto de factores primos

$n=\prod _{i=1}^r{p}_i^{k_i}$.

O número enteiro Modelo:Mvar é múltiplo de Modelo:Mvar se e só se a descomposición de Modelo:Mvar nun produto de factores primos contén polo menos cada Modelo:Mvar elevado a unha potencia Modelo:Mvar maior ou igual a Modelo:Mvar.

O enteiro Modelo:Mvar é un divisor de Modelo:Mvar se e só se existen Modelo:Mvar enteiros Modelo:Mvar que satisfán Modelo:Math tal que

$d=\prod _{i=1}^r{p}_i^{k{\text{'}}_i}$.

Nesta forma, entón é posíbel facer unha lista de todos os divisores de Modelo:Mvar 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 Modelo:Mvar 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 Modelo:Mvar e Modelo:Mvar maiores ou iguais a 2 calcúlase mediante o produto dos factores primos que aparecen tanto na descomposición de Modelo:Mvar como de Modelo:Mvar provistos do menor dos expoñentes atopados na descomposición de Modelo:Mvar e Modelo:Mvar. Entón,

$\mathrm{s}\mathrm{e}a=2^3\times 3^4\times 5^2\times 7\mathrm{e}b=2^2\times 3^5\times 7^3\times 11\mathrm{d}\mathrm{a}\mathrm{q}\mathrm{u}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{m}\mathrm{c}\mathrm{d}(a,b)=2^2\times 3^4\times 7.$

O MCM (mínimo común múltiplo) de dous números enteiros Modelo:Mvar e Modelo:Mvar maiores ou iguais a 2 calcúlase como o produto dos factores primos que aparecen en Modelo:Mvar ou en Modelo:Mvar provistos do maior dos expoñentes atopados na descomposición de Modelo:Mvar e de Modelo:Mvar. Entón,

$\mathrm{s}\mathrm{e}a=2^3\times 3^4\times 5^2\times 7\mathrm{e}b=2^2\times 3^5\times 7^3\times 11\mathrm{d}\mathrm{a}\mathrm{q}\mathrm{u}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{m}\mathrm{c}\mathrm{m}(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íz (matemáticas)|raíces Modelo:Mvar-é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 5}{2^2\times 7\times 5}+\frac{3\times 2}{2\times 5\times 7\times 2}=\frac{31}{2^2\times 5\times 7}=\frac{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 Modelo:Mvar-é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 Modelo:Mvar divide Modelo:Mvar. Se un primo si o divide, comezamos de novo o algoritmo para Modelo:Math, 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

2088	2		2 divide 2088 o cociente é 1044
1044	2		2 divide 1044, o cociente é 522
522	2		2 divide 522, o cociente é 261
261	3		2 non divide 261, pero 3 divide 261 e o cociente é 87
87	3		3 divide 87 e o cociente é 29
29			nin 3 nin 5 dividen a 29 e 7^2 é maior que 29 (final)

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

Estado actual da arte

Se un número grande de Modelo:Mvar 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(n^k) calquera que sexa a constante Modelo:Mvar. Non entanto, hai algoritmos que son tan rápidos como Θ(eⁿ) (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)

Véxase tamén

Bibliografía

• Modelo:Cita libro Chapter 5: Exponential Factoring Algorithms, pp. 191–226. Chapter 6: Subexponential Factoring Algorithms, pp. 227–284. Section 7.4: Elliptic curve method, pp. 301–313.
• Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. Modelo:ISBN. Section 4.5.4: Factoring into Primes, pp. 379–417.
• Modelo:Cita libro.
• Modelo:Cita libro

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