Ver o código fonte de «Factorización de enteiros»

[[Ficheiro:PrimeDecompositionExample.svg|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úmero primo|números primos]]. Por exemplo, se o número dado é 45, a factorización en primos é <math>45 = 3^2 \cdot 5 = 3 \cdot 3 \cdot 5  </math>.

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

<math>\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}</math>

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 [[Divisor|de divisibilidade]], [[Fracción (matemáticas)|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 {{Mvar|n}} maior ou igual a 1<ref>{{cita libro|author=[[Louis Comtet]]|title=Analyse combinatoire élémentaire|p=68}}</ref>, existe unha [[Tupla|secuencia finita]] única {{math|(''p''{{sub|1}}, ''k''{{sub|1}}) … (''p{{sub|r}}'', ''k{{sub|r}}'')}} tal que:

# os {{Mvar|p{{sub|i}}}} son números primos tal que, se {{Math|''i'' < ''j''}}, entón {{Math|''p{{sub|i}}'' < ''p{{sub|j}}''}};
# os {{Mvar|k{{sub|i}}}} son enteiros naturais distintos de cero;
# {{Mvar|n}} é o produto dos números {{Mvar|p{{sub|i|}}{{sup|k{{sub|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 {{Mvar|n}} en produto de factores primos
:<math>n=\prod_{i=1}^rp_i^{k_i}</math>.
O número enteiro {{Mvar|m}} é múltiplo de {{Mvar|n}} se e só se a descomposición de {{Mvar|m}} nun produto de factores primos contén polo menos cada {{Mvar|p{{sub|i}}}} elevado a unha potencia {{Mvar|k'{{sub|i}}}} maior ou igual a {{Mvar|k{{sub|i}}}}.

O enteiro {{Mvar|d}} é un divisor de {{Mvar|n}} se e só se existen {{Mvar|r}} enteiros {{Mvar|k{{sub|i}}'}} que satisfán {{Math|0 ≤ ''k'{{sub|i}}'' ≤ ''k{{sub|i}}''}} tal que 
:<math>d=\prod_{i=1}^rp_i^{k'_i}</math>.

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

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

A [[Función suma de divisores|suma dos divisores positivos]] de {{Mvar|n}} vén dada pola fórmula 
:<math>\sigma(n)=\prod_{i=1}^r\frac{p_i^{k_i + 1}-1}{p_i-1}</math>

=== MCD e MCM ===
O [[Máximo común divisor|MCD]] (máximo común divisor) de dous números enteiros {{Mvar|a}} e {{Mvar|b}} maiores ou iguais a 2 calcúlase mediante o produto dos factores primos que aparecen tanto na descomposición de {{Mvar|a}} ''como de'' {{Mvar|b}} provistos do ''menor'' dos expoñentes atopados na descomposición de {{Mvar|a}} e {{Mvar|b}}. Entón, 
:<math>{\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.</math>

O [[Mínimo común múltiplo|MCM]] (mínimo común múltiplo) de dous números enteiros {{Mvar|a}} e {{Mvar|b}} maiores ou iguais a 2 calcúlase como o produto dos factores primos que aparecen en {{Mvar|a}} ''ou'' en {{Mvar|b}} provistos do ''maior'' dos expoñentes atopados na descomposición de {{Mvar|a}} e de {{Mvar|b}}. Entón, 
:<math>{\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.</math>

=== Formas reducidas ===
A descomposición en factores primos pode ser útil para reducir unha fracción a [[Fracción irredutible|unha fracción irredutíbel]], para [[Descomposición en fraccións simples|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 {{Mvar|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: 
:<math>\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}</math>

==== 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: 
:<math>\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}</math>

==== 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: 
:<math>\sqrt{4752}=\sqrt{2^4\times 3^3\times 11}=\sqrt{(2^2\times 3)^2\times 3\times 11}=12\sqrt{33} </math>.

Esta propiedade xeneralízase ás raíces {{Mvar|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 {{Mvar|p}} divide {{Mvar|n}}. Se un primo si o divide, comezamos de novo o algoritmo para {{Math|''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
{| class="wikitable"
| style="text-align:right" |2088
| style="text-align:left;border-left:thin solid black" | 2
|
| ''2 divide 2088 o cociente é 1044''
|-
| style="text-align:right" | 1044
| style="text-align:left;border-left:thin solid black" | 2
|
| ''2 divide 1044, o cociente é 522''
|-
| style="text-align:right" | 522
| style="text-align:left;border-left:thin solid black" | 2
|
| ''2 divide 522, o cociente é 261''
|-
| style="text-align:right" | 261
| style="text-align:left;border-left:thin solid black" | 3
|
| ''2 non divide 261, pero 3 divide 261 e o cociente é 87''
|-
| style="text-align:right" | 87
| style="text-align:left;border-left:thin solid black" | 3
|
| ''3 divide 87 e o cociente é 29''
|-
| style="text-align:right" | 29
| style="text-align:left;border-left:thin solid black" |
|
| ''nin 3 nin 5 dividen a 29 e 7^2 é maior que 29 (final)''
|}
Obtemos a descomposición esperada: <math>2088=2^3 \cdot 3^2 \cdot 29.</math>

=== Estado actual da arte ===
Se un número grande de {{Mvar|n}} [[Bit|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 [[Notatción O grande|O]](''n<sup>k</sup>'') calquera que sexa a constante {{Mvar|k}}. Non entanto, hai algoritmos que son tan rápidos como [[Comparación aristótica|Θ]](e<sup>''n''</sup>) (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 [[Congruencia de cadrados|da congruencia de cadrados]].

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

== Notas ==
{{reflist|30em}} 

== Véxase tamén ==
=== Bibliografía ===
* {{cita libro
|author = [[Richard Crandall]] e [[Carl Pomerance]]
| year = 2001
| title = Prime Numbers: A Computational Perspective
|url = https://archive.org/details/primenumberscomp0000cran
| publisher = Springer
| isbn = 0-387-94777-9}} 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. {{ISBN|0-201-89684-2}}. Section 4.5.4: Factoring into Primes, pp.&nbsp;379–417.
* {{cita libro | author =Samuel S. Wagstaff Jr. | title=The Joy of Factoring | publisher=American Mathematical Society | location=Providence, RI | year=2013 | isbn=978-1-4704-1048-3 |url=https://www.ams.org/bookpages/stml-68 |author-link=Samuel S. Wagstaff Jr. }}.
* {{cita libro |title=[[Hacker's Delight]] |first=Henry S. Jr. |last=Warren |date=2013 |edition=2 |publisher=[[Addison Wesley]] - [[Pearson Education, Inc.]] |isbn=978-0-321-84268-8}}

=== Outros artigos ===
* [[Factorización]]
* [[Número p-ádico]]
* [[Algoritmo_de_Shor]]

=== Ligazóns externas ===
* [https://www.cuemath.com/numbers/prime-factorization/ Prime factorization Cuemath].
* [[Manindra Agrawal]], Neeraj Kayal, Nitin Saxena, "PRIMES is in P." Annals of Mathematics 160(2): 781–793 (2004). [http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf August 2005 version PDF]
* [https://www.alpertron.com.ar/ECM.HTM Dario Alpern Calculadora online para factorizar enteiros grandes] 

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