Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

The Exponentiation of (not-so) Large Primes

by titivillus (Beadle)
on Oct 02, 2002 at 14:35 UTC ( #202287=perlquestion: print w/ replies, xml ) Need Help??
titivillus has asked for the wisdom of the Perl Monks concerning the following question:

I am trying to make a perl script that does RSA using trivially small primes (I'm specifically using the primes Bruce Schneier uses in his example in Applied Cryptography) in order to keep the problem down to a point where it fits (more or less) in the human brain. The problem is, in the code I'm doing, I'm ending up having to find ( 1019**1019 ) % 3337, and 1019**1019 blows the top off perl's default integer implementation (1019**103 pretty much gets you infinity) so getting the mod of infinity is a no-goer.

I've looked into Math::BigInt, but it has no exponentiation according to my work Perl docset. I realize that 1000**1019 is essentially 1 followed by 3069 zeroes, but I'm not seeing a clever way of handling this. I'd prefer pure perl solutions.

Comment on The Exponentiation of (not-so) Large Primes
Re: The Exponentiation of (not-so) Large Primes
by hiseldl (Priest) on Oct 02, 2002 at 14:42 UTC
    If you look at the source of Math::BigInt.pm, you will find
    '**' => sub {new Math::BigInt $_[2]? bpow($_[1],${$_[0]}) : bpow(${$_[0]},$_[1])},
    in the operator overload section. This is the operation that I used in a project where I did about the same thing as you are doing.

    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!

Re: The Exponentiation of (not-so) Large Primes
by BrowserUk (Pope) on Oct 02, 2002 at 15:18 UTC

    Or you could just do

    use constant N1019xx1019mod3337 => 54;

    Cor! Like yer ring! ... HALO dammit! ... 'Ave it yer way! Hal-lo, Mister la-de-da. ... Like yer ring!
Re: The Exponentiation of (not-so) Large Primes
by Abigail-II (Bishop) on Oct 02, 2002 at 16:03 UTC
    Just make use of the fact that:
    (a * b) % c = ((a % c) * (b % c)) %c

    So,

    (1019 ** 1019) % 3337 = ((1019 ** 2) * (1019 ** 1017)) % 3337 = (((1019 ** 2) % 3337) * (1019 ** 1017) % 3337)) % 3337

    which shouldn't be too hard to continue.

    Abigail

Re: The Exponentiation of (not-so) Large Primes
by abell (Chaplain) on Oct 02, 2002 at 16:51 UTC
    As hinted by Abigail-II, exponentiating mod a number is better accomplished by keeping the numbers reduced at every step. The straightforward algorithm would be
    # 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; }

    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; }

    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
    


    Best regards

    Antonio Bellezza

    The stupider the astronaut, the easier it is to win the trip to Vega - A. Tucket
Re: The Exponentiation of (not-so) Large Primes
by hsmyers (Canon) on Oct 02, 2002 at 19:54 UTC
      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."
Re: The Exponentiation of (not-so) Large Primes
by thor (Priest) on Oct 02, 2002 at 23:01 UTC
    I took a crypto class at the University of Minnesota. We covered a neat algorithm that can be found here. If I remember correctly, it's O(log(n)). You should be able to extend it to use Math::BigInt objects should you desire.

    thor

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://202287]
Approved by cacharbe
Front-paged by SparkeyG
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (19)
As of 2014-07-11 16:03 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    When choosing user names for websites, I prefer to use:








    Results (231 votes), past polls