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
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++;
}
JP Bourget (punklrokk)
MS Information and Security
Rochester Institute of Technology
Rochester, NY