There's a bmodpow method in Math::BigInt,
that calculates a power of a number over a modulus.
(I think this would still be a very slow primality test
that way.)
Update: or you could leave M::BI out altogether
and use a hand-rolled modpow function, such as
sub modpow { my($b, $p, $m) = @_; my $r = 1; for (;;) { $p & 1 and $r
+= ($r * $b) % $m; 0 < ($p >>= 1) or last; $b = ($b * $b) % $m; } $r;
+}
$s = 0; for $n (2..1000) { modpow($_, $n - 1, $n) != 1 and goto G for
+2 .. $n - 1; print $n, " appears to be prime ", ++$s, "\n"; G: }
Update:
or, without the goto:
sub modpow { my($b, $p, $m) = @_; my $r = 1; for (;;) { $p & 1 and $r
+= ($r * $b) % $m; 0 < ($p >>= 1) or last; $b = ($b * $b) % $m; } $r;
+} $s = 0;
G: for $n (2..1000) { modpow($_, $n - 1, $n) != 1 and next G for 2 ..
+$n - 1; print $n, " is prime number ", ++$s, "\n"; }
|