sábado, 14 de marzo de 2015

criptografía - algoritmos criptográficos

método de factorización de Euler es un método de factorización basado en la representación de un entero positivo N como la suma de dos cuadrados de dos maneras distintas:
N = a^2+ b^2 = c^2+ d^2
Aunque la factorización algebraica de números binomiales no sirve para factorizar sumas de dos cuadrados (en efecto un número que se puede expresar de una forma como suma de dos cuadrados es un número primo) si se pueden hallar dos representaciones distintas de un número como suma de dos cuadrados se sigue de ahí una factorización:
Partiendo de N = a^2 + b^2 = c^2 + d^2
se resta b^2+c^2 a ambos lados de la igualdad para crear una diferencia de dos cuadrados:
a^2 - c^2 = d^2 - b^2
y de ahí se sigue que:
(a - c)\cdot(a + c) = (d - b)\cdot(d + b)
Supóngase sin pérdida de generalidad que d y b son ambos pares o bien ambos impares, de forma que su diferencia es par. Ahora se define una constante k igual al máximo común divisor de (a - c) y (d - b) de forma que:
(a - c) = kl y (d - b) = km, con \operatorname{mcd}(l, m) = 1
de forma que, tras sustituir en la expresión anterior quedaría la siguiente ecuación:
l\cdot(a + c) = m\cdot(d + b)
Como l y m son primos entre sí, se supone que (a + c) es divisible por m, lo que nos daria como expresiones:
(a + c) = mn y;
(d + b) = ln
La factorización del número original N se puede mostrar que podría ser igual a:
N = \left[\left(\frac{k}{2}\right)^2 + \left(\frac{n}{2}\right)^2\right]\cdot(m^2 + l^2)

La idea de que dos representaciones distintas de un entero positivo diera lugar a una factorización fue aparentemente planteada por primera vez por Marin Mersenne un loco matemático que le gustaba experimentar con los números y letras (Algebra). Sin embargo, no fue hasta Euler, cien años después y un poco más, que su uso empezara a extenderse. Su más celebrado uso del método que hoy lleva su nombre fue el de factorizar el número N = 1000009, que, al parecer, se pensaba que era primo a pesar de que ninguno de los principales tests de primalidad lo da como pseudoprimo.
Como también:
1000009 = 1000^2 + 3^2 = 972^2 + 235 ^2
se tiene por las fórmulas anteriores:
a = 1000a - c = 28k = 4
b = 3a + c = 1972l = 7
c = 972d - b = 232m = 58
d = 235d + b = 238n = 34
Así,
\begin{align} 1000009 & = \left[\left(\frac{4}{2}\right)^2 + \left(\frac{34}{2}\right)^2\right]\cdot(58^2 + 7^2) \\ {} & = (2^2 + 17^2)\cdot(58^2 + 7^2) \\ {} & = (4 + 289)\cdot(3364 + 49) \\ {} & = 293\cdot3413 \end{align}
El método de factorización de Euler es más efectivo que el de Fermat para números naturales cuyos factores no sean próximos entre sí y es potencialmente mucho más eficiente que la división por tentativa si se pueden hallar representaciones de números como suma de cuadrados de forma razonablemente fácil. El desarrollo de Euler permitió una factorización mucho más eficiente, y, para los años 1910, el desarrollo de una tabla de factores de números hasta 10 millones. Los métodos empleados para encontrar representaciones de números como sumas de dos cuadrados son esencialmente los mismos que se usan para encontrar las diferencias de cuadrados en el método de Fermat.


Ejemplos adicionales


  1. Utilice el Método de Fermat para hallar la factorización prima de
    \begin{displaymath} \begin{array}[c]{cccccccc}% a) & 4757 & & f) & 2873 & & k) &... ...,007\\ e) & 15\,553 & & j) & 12\,827 & & p) & 3127 \end{array}\end{displaymath}

  2. Utilice los métodos de factorización vistos para halla la factorización prima de
    \begin{displaymath} \begin{array}[c]{cccccccc}% a) & 342 & & d) & 190\,045 & & g... ...5\\ c) & 9776 & & f) & 420\,042 & & i) & 6374\,680 \end{array}\end{displaymath}

  3. A partir del método de factorización utilizado para factorizar $ 3131$ (en el ejemplo % latex2html id marker 4838 $ \ref{ej6}$ ), deduzca una factorización de los siguientes tipos de números escritos en base $ 10:$
    \begin{displaymath} \begin{array}[c]{ccccc}% a) & \left( ababab\right) & & d) & ... ...eft( ab0ab\right) & & f) & \left( ab00ab00ab\right) \end{array}\end{displaymath}
     

 Solución

1.\begin{displaymath}% \begin{array}[c]{cccccccc}% a) & 67\cdot71 & & f) & 13^{2}\... ...103\cdot151 & & j) & 127\cdot101 & & p) & 59\cdot53 \end{array}\end{displaymath}
  
2.\begin{displaymath}% \begin{array}[c]{cccccccc}% a) & 2\cdot3^{2}\cdot19 & & d) ... ...) & 2^{3}\cdot5\cdot13^{2}\cdot23\cdot41 \end{array}\allowbreak\end{displaymath}
  
3.$ \allowbreak \begin{array}[c]{ccccc}% a) & \left( ab\right) \cdot\left( 10101\r... ... 1001\right) & & f) & \left( ab\right) \cdot\left( 100010001\right) \end{array}$


  1. Utilice el Método de Euler para hallar la factorización prima de
    \begin{displaymath} \begin{array}[c]{cccccccc}% a) & 221 & & f) & 2813 & & k) & ... ...o) & 6409\\ e) & 3293 & & j) & 2929 & & p) & 38077 \end{array}\end{displaymath}

  2. Utilice los métodos de factorización vistos para halla la factorización prima de
    \begin{displaymath} \begin{array}[c]{ccccc}% a) & 43\,018 & & d) & 793\,793\\ b... ...& e) & 7280\,728\\ c) & 79\,566 & & f) & 6630\,663 \end{array}\end{displaymath}


Solución

1.\begin{displaymath}% \begin{array}[c]{cccccc}% a) & 13\cdot17 & f) & 97\cdot29 &... ...7\cdot89 & j) & 29\cdot101 & p) & 13\cdot29\cdot101 \end{array}\end{displaymath}
2.\begin{displaymath}% \begin{array}[c]{ccccc}% a) & 2\cdot137\cdot157 & & d) & 7\... ...f) & 3\cdot17\cdot13\cdot137\cdot73 \end{array}\medskip\medskip\end{displaymath}


Los números primos menores que 200


\begin{displaymath} \begin{array}[c]{ccccccccccc}% 2 & & 23 & & 59 & & 97 & & 13... ... & 167 & & \\ 19 & & 53 & & 89 & & 131 & & 173 & & \end{array}\end{displaymath}
Publicado por en

No hay comentarios:

Publicar un comentario

Suscribirse a: Enviar comentarios (Atom)