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{aligned}&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{aligned}}$

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 $n$ maior ou igual a 1^[1], existe unha secuencia finita única $(p 1, k 1) \dots (p r, k r)$ tal que:

os $p i$ son números primos tal que, se $i < j$ , entón $p i < p j$ ;
os $k i$ son enteiros naturais distintos de cero;
$n$ é o produto dos números $p i k i$ .

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 $n$ en produto de factores primos

n=\prod _{i=1}^{r}p_{i}^{k_{i}}

.

O número enteiro $m$ é múltiplo de $n$ se e só se a descomposición de $m$ nun produto de factores primos contén polo menos cada $p i$ elevado a unha potencia $k' i$ maior ou igual a $k i$ .

O enteiro $d$ é un divisor de $n$ se e só se existen $r$ enteiros $k i'$ que satisfán $0 \leq k' i \leq k i$ tal que

d=\prod _{i=1}^{r}p_{i}^{k'_{i}}

.

Nesta forma, entón é posíbel facer unha lista de todos os divisores de $n$ 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 $n$ 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 $a$ e $b$ maiores ou iguais a 2 calcúlase mediante o produto dos factores primos que aparecen tanto na descomposición de $a$ como de $b$ provistos do menor dos expoñentes atopados na descomposición de $a$ e $b$ . 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 $a$ e $b$ maiores ou iguais a 2 calcúlase como o produto dos factores primos que aparecen en $a$ ou en $b$ provistos do maior dos expoñentes atopados na descomposición de $a$ e de $b$ . 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 $n$ -é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 $n$ -é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 $p$ divide $n$ . Se un primo si o divide, comezamos de novo o algoritmo para $n / p$ , 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 $n$ 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 $k$ . 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)

Notas

↑ Louis Comtet. Analyse combinatoire élémentaire. p. 68.

Véxase tamén

Bibliografía

Richard Crandall e Carl Pomerance (2001). Prime Numbers: A Computational Perspective. Springer. ISBN 0-387-94777-9. 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. ISBN 0-201-89684-2. Section 4.5.4: Factoring into Primes, pp. 379–417.
Samuel S. Wagstaff Jr. (2013). The Joy of Factoring. Providence, RI: American Mathematical Society. ISBN 978-1-4704-1048-3. .
Warren, Henry S. Jr. (2013). Hacker's Delight (2 ed.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8.

Outros artigos

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

[1] Louis Comtet. Analyse combinatoire élémentaire. p. 68.

[1]