Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Mcd extendido

5 views
Skip to first unread message

Manuel

unread,
May 25, 2012, 11:16:39 AM5/25/12
to
La pregunta es:
Cuantos pasos son necesarios para hacer el calculo con numeros de 256
bits.

En el peor de los casos.

gracias.

Antonio González

unread,
May 25, 2012, 6:07:14 PM5/25/12
to
El 25/05/2012 17:16, Manuel escribi�:
�Qu�, intentando desencriptar el algoritmo RSA?

--
Antonio

Manuel

unread,
May 26, 2012, 7:08:20 PM5/26/12
to
jajaj, que perspicaz, Ya hace años que le doy vueltas a la manera de
factorizar esos numeros.
Pero en este caso, estoy haciendo una calculadora que trabaja con esos
numeros(en tamaño) bueno, esta version en particular es
para numeros de hasta 16384 bits.

y la pregunta es por que no estoy seguro del tamaño del bufer para
hacer ese calculo.

; A B r1 r2 r3 r4 Mcd(126,35) =
7 = 2*126 - 7*35
; mcd_d 126 35 21 14 7 0
; mcd_q 3 1 1 2
; mcd_x 1 0 1 -1 2 -5 x = 2
; mcd_y 0 1 -3 4 -7 18 y = -7

El algoritmo que uso es como este ejemplo. Que supongo ya conoces.

Pero no se como calcular el numero de pasos maximo para A,B

Gracias.

José H. Nieto

unread,
May 26, 2012, 8:12:15 PM5/26/12
to
Si los números no superan a F_n (número de Fibonacci) el algoritmo de
Euclides se lleva a lo sumo n-2 pasos. El peor caso se da para hallar
mcd(F_n,F_{n-1}). Como F_n es aproximadamente fi^n/rq(5), es fácil
calcular lo que quieres.

jhn




Manuel

unread,
May 27, 2012, 12:37:16 AM5/27/12
to
Gracias, ya me quedo bien claro el tema, creia que el numero de pasos
serian aprox. lg2(n)/2, pero no,
creo que se acerca bastante a lg2(n)

gracias de nuevo.
Manuel.

Manuel

unread,
May 27, 2012, 12:43:09 AM5/27/12
to
On 27 mayo, 02:12, José H. Nieto <jhni...@gmail.com> wrote:
Parece que no se publico mi respuestA..?

Ya me quedo claro, creia que el numero de pasos seria nBits/2, pero no
creo que se aproxima bastante a nBits.
Sabiendo esto, ya afinare probando con algunos calculos.

Gracias.
Manuel
0 new messages