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

In reply to optimizing the miller-rabin algorithm by punklrokk

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.