Factorización de enteiros

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 é .

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

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
.
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 
.

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: 
, 
é dicir, 6 divisores. 

A suma dos divisores positivos de  vén dada pola fórmula 

 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, 

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, 

 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: 

 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: 

 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: 
.

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
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: 

 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 Θ(en) (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. 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. . Section 4.5.4: Factoring into Primes, pp. 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 

Categoría:Aritmética
Categoría:Álxebra
Categoría:Teoría de números
Categoría:Wikipedia:Páxinas con traducións non revisadas