punklrokk has asked for the wisdom of the Perl Monks concerning the following 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.my $tempA = Math::BigInt>new($a); $b = $tempA>bmodpow($M,$n); #set b = a^m
JP Bourget (punklrokk) MS Information and Security Rochester Institute of Technology Rochester, NYuse 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 (9100093000) 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=$n1; 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<($n1);$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==($n1)) { #print "\$btemp=$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++; }


Replies are listed 'Best First'.  

Re: optimizing the millerrabin algorithm
by rhesa (Vicar) on May 16, 2006 at 03:41 UTC  
by syphilis (Bishop) on May 16, 2006 at 07:59 UTC  
Re: optimizing the millerrabin algorithm
by GrandFather (Saint) on May 16, 2006 at 01:46 UTC  
by punklrokk (Scribe) on May 16, 2006 at 01:57 UTC  
by GrandFather (Saint) on May 16, 2006 at 02:09 UTC  
by ikegami (Pope) on May 16, 2006 at 17:07 UTC  
Re: optimizing the millerrabin algorithm
by ForgotPasswordAgain (Priest) on May 16, 2006 at 10:54 UTC  
by Limbic~Region (Chancellor) on May 16, 2006 at 16:39 UTC 