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:

my $tempA = Math::BigInt->new($a); 
$b = $tempA->bmodpow($M,$n);      #set b = a^m
[download]

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.

use Math::BigInt;     #allows big integers needed for this algorithm


$x=$k=0;
#$M=$ARGV[0]-1;
#$n=$ARGV[0];                         #testing variable

$data_file="primelist.txt";     #imports known primes (91000-93000)
open(DAT, $data_file) || die("Could not open file!");
@raw_data=<DAT>;
close(DAT);

foreach $line(@raw_data) { #puts text file into a stepped array @prime
    $tempPrime=$line;
    @prime = split(/:/, $line);
}
# foreach $line(@prime) {    #makes sure primes are loaded in array
# print "$line\n";
# }




    
for ($n=91001; $n<93000; $n++) {
    $counter=0;
    $M=$n-1;
    print "\$n: $n\n";
    while ($M%2 != 1) {      # Loop to calculate $M and $k (2^k*M)
        $M=$M/2;
        $k+=1;
        #print "K=$k, M=$M\n";
        }
    for($a = 2; $a<($n-1);$a++){
         my $tempA = Math::BigInt->new($a);
         $b = $tempA->bmodpow($M,$n);      #set b = a^m mod n
         #print "\$b=$b\n";                 #tells us what b is
                 
        if ($b==1) {                     #test 1 (does b=1?)
            #print "$n: Prime (test1)\n";
            $counter++;
        } else {  
        
        for ($i=0; $i<$k; $i++) {
            if ($b==($n-1)) {
                #print "\$b-temp=$b\n";
                $counter++;
                #print "$n is a prime (test2)\n";
                last;                     #exits loop upon $b==1
                
            } else {
                $tempB = Math::BigInt->new($b);
                $b = $tempB->bmodpow(2,$n);
                #print "$b\n";
                #print "$n is composite\n";
                }                                                   
            }                                                         
+ 
                                        #print "\$a\=: $a\n";
        }
    }
    $ticker[$n]=$counter;    #Keep track of number of false positives
    $percentage[$n]=$counter/$n;        #Figure out percentage
    print "Counter: $ticker[$n]\n";
    print "Percentage: $percentage[$n]\n";
    $n++;
}
[download]

JP Bourget (punklrokk) MS Information and Security Rochester Institute of Technology Rochester, NY

---

---

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:

  <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>

• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or How to display code and escape characters are good places to start.