|Don't ask to ask, just ask|
optimizing the miller-rabin algorithmby punklrokk (Beadle)
|on May 16, 2006 at 00:47 UTC||Need Help??|
punklrokk has asked for the
wisdom of the Perl Monks concerning the following question:
Hello Monks! I am trying to optimize my code for the Miller-Rabin algorithm. (Finds prime numbers.) My friend did it in Java, and it took him 6 minutes, 18 seconds. (For his algorithm to run.) Mine looks like it'll take 2000 min, about 2 minutes per number; although in java. With out explaining the code too much, here's my question:
How can I figure out a better, either more efficient, or just faster running function, (does one exist?) to do this modular exponentiation? I am going to try sqare and multiply, but I'm wondering if the monks have a better way to do what I'm trying.
Disclaimer: This is a homework related question, but I have already completed the assignment, and I want to learn how to better optimize this algorithm. It's also a crypto course, not a Perl, or programming course. I've chosen this course as an opportunity to learn Perl.
JP Bourget (punklrokk) MS Information and Security Rochester Institute of Technology Rochester, NY