search

UC-IIC3253 / 2021

Repositorio del curso Criptografı́a y Seguridad Computacional - IIC3253
21 stars 3 forks source link

[Tarea2] Pregunta 2 l=1000 #37

Open Arcoirisky opened 3 years ago

Arcoirisky commented 3 years ago

no fue tanto como creía: image

un primo de l=1000 (por si alguien quiere mirar si le da): 9747107968567381219932339802722317011916997762394625642808868969673280772993228592080176137152803482993342258409248181389285756520888857718149804788013354928177810672475820852980899455173774155697766468236493893606171298434660268867811400485817809241128353115627197194763384402218221326034080363552819694609925444999196762381586595048832726310237396146200598134544867289730855047177647312597341782668958899661194734140678339103611630277034813780035363535263455723100009451385411219071268678428207700109159900516915425489822212922786288172956558742771669121437444244995040747798340923591405902758710571634604665422664797550273865204017037992116536962113385536316555894802554832568813550987101442636557499106631617915939260310539429658248840951968234860707969545351161226971936437557617609294212850613838650045327746762253147556310826287902990564675492963799547099281587262113721184110096676868708667002393591476483526554265926874459899019281256202257838093235314235265733976102392501598454448875459279

a mi programa le tomó casi 3 minutos encontrarlo :shipit:

VicenteMerino commented 3 years ago

@Arcoirisky Esto para verificar si es primo?

Arcoirisky commented 3 years ago

@VicenteMerino claro, si quieren xD es lo que habíamos hablado al final de la clase de hoy

VicenteMerino commented 3 years ago

En mi caso se me demoró como 20 segundos aprox, pero tuve que aumentarle el Recursion Limit.

Arcoirisky commented 3 years ago

Verificar q ese número es primo con k = 100 (para el error del enunciado) me tomó 0,3 seg o: Los 20seg que dices es en generar el primo l=1000? brigido qué clase de magia negra hiciste 😱

VicenteMerino commented 3 years ago

Aaaah, en ese caso no se, pero me suena a que si debería ser alto.

Arcoirisky commented 3 years ago

Agree y mi computador lo sabe 👌🏼

mugartec commented 3 years ago

Muy buena discusión :smiley: Sólo quería comentarles que (si tienen tiempo) traten de hacer todo sin usar recursión, queda más eficiente y nunca se va a caer por overflow. Si tienen dudas de cómo hacerlo lo podemos conversar. Saludos!

VicenteMerino commented 3 years ago

@mugartec A mi se me cae al momento de hacer la exponenciación rápida, aunque creo que vi por internet una versión del algoritmo con un while en vez de recursión, debería tratar de cambiarlo por esto?

Arcoirisky commented 3 years ago

Nunca antes había escuchado que sin recursión es más eficiente, aunque todo lo que tengo es iterativo y no se me cae

Arcoirisky commented 3 years ago

incluso para la exponenciación rápida, lo más "rápido" o llamativo que he visto es un algoritmo iterativo donde trabajan con el binario de los números. Usando shifts y &, siendo equivalente a las operaciones básicas de toda la vida o:

lfuenzalida2 commented 3 years ago

incluso para la exponenciación rápida, lo más "rápido" o llamativo que he visto es un algoritmo iterativo donde trabajan con el binario de los números. Usando shifts y &, siendo equivalente a las operaciones básicas de toda la vida o:

Tremendo link, cambié un par de operaciones que hacia por sus equivalentes en el link y mi programa corre 4 veces mas rapido