Wikilibros

Diferencia entre revisiones de «Implementación de algoritmos de teoría de números/Algoritmo de factorización en números primos»

Explorar historial interactivamente
← Edición anteriorEdición siguiente →
Contenido eliminado Contenido añadido
VisualWikitexto
Raulshc (discusión | contribs.)
268 ediciones
+reescritura de las notas usando el contenido original
Línea 22:
</pre>
 
Otro, similar pero que consiste en iterar hasta la raíz cuadrada de N [<refsmall>Un[[Implementación númerode compuestoalgoritmos (llamemoslode C)teoría node puede tener másnúmeros/Algoritmo de un factor primo que seafactorización mayoren anúmeros suprimos#Nota raíz1|Nota cuadrada1]]</brsmall>]
</br>▼
Dem: Supongamos que sí puede haber más de uno. Llamemos A y B a esos dos números primos. Llamemos P1, P2,.. Pn al resto de los números primos factores de C.</br>▼
Sea dA = A - raizcuad (C)</br>
Sea dB = B - raizcuad (C)</br>
Si A y B son mayores que la raíz cuadrada de C, entonces dA y dB serán positivos</br>
Entonces C = A*B*P1*P2... = (raizcuad (C)+dA)*(raizcuad (C)+dB)*P1*P2... = (raizcuad (C)*raizcuad (C) + dA*raizcuad (C) + dB*raizcuad (C) + dA*dB)*P1*P2... = (C + (dA+dB)*raizcuad (C) + dA*dB)*P1*P2...</br>
C*P1*P2.. + (dA+dB)*raizcuad (C)*P1*P2... + dA*dB*P1*P2...</br>
Obviamente, toda esa suma es mayor a C. Como partimos diciendo que C era igual a esa suma llegamos a una contradicción</br>
Por lo tanto, a lo sumo un factor puede ser mayor que la raíz cuadrada de C.</br>▼
</ref>
 
<pre>
Línea 50 ⟶ 40:
</pre>
 
Otro, que combina ambos, consiste en, además, ir incrementando i de a 2, 4, 2, 4..[<refsmall>Los[[Implementación númerosde primosalgoritmos (mayoresde queteoría 3)de pueden expresarsenúmeros/Algoritmo de lafactorización siguienteen forma:números primos#Nota 6n±1|Nota (siendo esta la más eficiente para soluciones iterativas de programación).2]]</brsmall>]
</br>
Dem: Todo número natural puede expresarse como 6n±r, para algún n. R variara solo entre 0 y 5.</br>▼
6n+0 es divisible por 6 SIEMPRE</br>▼
6n+2 es divisible por 2 SIEMPRE</br>▼
6n+3 es divisible por 3 SIEMPRE</br>▼
6n+4 es divisible por 2 SIEMPRE</br>▼
6n+1 y 6n-1 (o lo que es lo mismo a efectos del análisis, 6n+5), no proporcionan ninguna garantía de divisibilidad, por lo tanto los números primos solo pueden encontrarse entre ellos).</br>▼
</ref>
 
<pre>
Línea 81 ⟶ 63:
 
== Notas ==
=== Nota 1 ===
{{Listaref}}
Un número compuesto <math>n</math> no puede tener más de un factor primo que sea mayor a su raíz cuadrada.
 
'''Demostración''':
▲Dem: Supongamos que sí puede haber más de uno, por ejemplo dos. Llamemos A<math>p_1</math> y B<math>p_2</math> a esos dos números primos. Llamemosy P1<math>p_3</math>, P2<math>p_4</math>,.. Pn<math>p_n</math> al resto de los números primos factores de C.<math>n</brmath>. Sean:
 
:<math>a = p_1-\sqrt{n}</math>
:<math>b = p_2-\sqrt{n}</math>
 
Si <math>p_1</math> y <math>p_2</math> ambos son mayores que <math>\sqrt{n}</math>, entonces <math>a</math> y <math>b</math> serán positivos. Desarrollando el producto se tiene que:
 
:<math>
\begin{align}
n & = p_1\cdot p_2\cdot p_3\cdot p_4 \cdots \\
{} & = (\sqrt{n}+a)\cdot (\sqrt{n}+b)\cdot p_3 \cdot p_4\cdots \\
{} & = (n+(a+b)\sqrt{n} + ab)\cdot p_3 \cdot p_4\cdots \\
\end{align}
▲</brmath>
 
Como <math>a>0</math> y <math>b>0</math>, el desarrollo <math>(a+b)\sqrt{n} + ab > 0</math>, por lo que el producto inicial debe ser mayor que
 
:<math>n < (n+(a+b)\sqrt{n} + ab)\cdot p_3 \cdot p_4\cdots</math>
 
▲y se llega a una contradicción. Por lo tanto, a lo sumo un factor puede ser mayor que la raíz cuadrada de C.<math>\sqrt{n}</brmath>.
 
=== Nota 2 ===
Los números primos mayores que 3 cumplen con la siguiente condición:
 
:<math>p \equiv 1 \pmod 6</math>
ó
:<math>p \equiv -1 \pmod 6</math>
 
siendo esta la más eficiente para soluciones iterativas de programación.
 
'''Demostración''':
 
▲Dem: Todo número natural puede expresarse como 6n6''n''±''r'', para algún ''n.'', R''r'' variaravariará solo entre 0 y 5.</br>
 
▲6n:6''n''+0 es divisible por 6 SIEMPRE</br>
▲6n:6''n''+2 es divisible por 2 SIEMPRE</br>
▲6n:6''n''+3 es divisible por 3 SIEMPRE</br>
▲6n:6''n''+4 es divisible por 2 SIEMPRE</br>
 
▲6n6''n''+1 y 6n6''n''-1 (o lo que es lo mismo a efectos del análisis, 6n6''n''+5), no proporcionan ninguna garantía de divisibilidad entre 6, por lo tanto los números primos solo pueden encontrarse entre ellos).</br>
 
[[Categoría:Libro:Implementación de algoritmos de teoría de números]]
Obtenido de «https://es.wikibooks.org/wiki/Implementación_de_algoritmos_de_teoría_de_números/Algoritmo_de_factorización_en_números_primos»