Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options
 
PerlMonks  

Re: modular exponentiation with arbitrary precision binary numbers (did I say RSA?)

by ton (Friar)
on Feb 20, 2001 at 01:25 UTC ( #59478=note: print w/ replies, xml ) Need Help??


in reply to modular exponentiation with arbitrary precision binary numbers (did I say RSA?)

Bit::Vector implements all of these methods except for bmodexp. Here is my stab at modular exponentiation using bit vectors:

sub _VectorModExp($$$) { my $baseV = shift; my $expV = shift; my $modV = shift; my $resultV; my $trashV; # Bruteforcing this takes way too much time when expV is huge (whi +ch is usually). # Instead, we'll compute using powers of 2. my $i; my $powerV = $baseV->Clone(); # for $i = 0, or baseV^(2^0) = ba +seV^1 = baseV if ($expV->contains($i)) { $resultV->Copy($powerV); } else { $resultV->Empty(); } for ($i = 1; $i < ($expV->Size()/2); ++$i) { return $resultV if (!$expV->Interval_Scan_inc($i)); $powerV->Multiply($powerV, $powerV); $trashV->Divide($powerV, $modV, $powerV); if ($expV->contains($i)) { if ($resultV->is_empty()) { $resultV->Copy($powerV); } else { $resultV->Multiply($resultV, $powerV); } $trashV->Divide($resultV, $modV, $resultV); } } return $resultV; }

Edit: 2001-03-03 by neshura


Comment on Re: modular exponentiation with arbitrary precision binary numbers (did I say RSA?)
Download Code
cool -- thanks!
by jhanna (Scribe) on Aug 30, 2001 at 02:27 UTC
    I didn't test it, but it looks good. Ok, so I withdraw my unformed remarks about vectors. j

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://59478]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (5)
As of 2014-10-23 04:38 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    For retirement, I am banking on:










    Results (124 votes), past polls