(a * b) % c = ((a % c) * (b % c)) %c
[download]

So,

  (1019 ** 1019) % 3337 =
 ((1019 ** 2) * (1019 ** 1017)) % 3337 =
(((1019 ** 2) % 3337) * (1019 ** 1017) % 3337)) % 3337
[download]

which shouldn't be too hard to continue.

Abigail

'**'    =>    sub {new Math::BigInt
               $_[2]? bpow($_[1],${$_[0]}) : bpow(${$_[0]},$_[1])},
[download]

The docs don't show **, but you should still be able to use it, because it's in the code. Or, you can call bpow(arg1, arg2) directly. :)

--
hiseldl
What time is it? It's Camel Time!

# modexp ( base, exp, n ) = base**exp mod n
sub modexp {
    my ($base, $exp, $n) = @_;
    die "Negative exponent" if $exp<0;
    my $res = 1;
    while ($exp>0) {
    $res = ( $res * $base ) % $n;
    $exp--;
    }
    return $res;
}
[download]

This has the disadvantage of being of linear complexity in the exponent. An algorithm linear in log($exp) is as follows:

sub binmodexp {
    my ($base, $exp, $n) = @_;
    die "Negative exponent" if $exp<0;
    my $res = 1;
    my $mul = $base % $n;
    while ($exp) {
    if ($exp & 1) {
        $res = ( $res * $mul ) % $n;
    }
    $exp>>=1;
    $mul = ($mul*$mul) % $n;
    }
    return $res;
}
[download]

It is based on the simple (but powerful) observation that if you have to take, say, the 37-th power of a number a, as 37 = 2^5 + 2^2 + 1, it is enough to multiply the factors

a,
a^(2^2) = (a^2) ^ 2
and
a^(2^5) = ((((a^2) ^ 2) ^ 2) ^ 2) ^ 2

Or you could just do

use constant N1019xx1019mod3337 => 54;
[download]

To quote http://world.std.com/~franl/crypto/rsa-guts.html

RSA in 2 Lines of Perl

Adam Back (aba@dcs.exeter.ac.uk) has created an implementation of RSA in just 2 lines of Perl. It uses <KBD>dc</KBD>, an arbritrary precision arithmetic package that ships with most UNIX systems. Here's the Perl code:

print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*"
+,<>
)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|
+dc`
[download]

--hsm

Yes, this is years late, but I'm just back from YAPC::NA and back in a Perl state of mind. I started out saying that I wanted a pure Perl implementation. The description you link to says.

It uses dc, an arbritrary precision arithmetic package that ships with most UNIX systems.

That isn't quite what I was hoping for. And, y'know? Those two-line implementations of things are exactly why people have a bad view of Perl. Yes, it's wonderful and cool that such a small implementation exists. But I was hoping to put this together for a presentation for my LUG, and having code that someone who isn't a full-on Perl guru can look at and understand is a good thing when you're trying to teach it. I don't want to be harsh -- you were trying to help -- and I do suck for abandoning this thought for four years. It's just that the cool 2-line implementation that calls dc isn't what I need.

.sig goes here

You are 100% correct! That said I would recommend the following for your presentation; go ahead and show the Perl code, explain your criticisms and then demonstrate a workable version either in Perl or (my choice) Mathematica. Perhaps a headline such as "When go answers go bad" or some such.

--hsm

"Never try to teach a pig to sing...it wastes your time and it annoys the pig."

thor