Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
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
Replies are listed 'Best First'.
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 surveying the Monastery: (16)
As of 2015-07-30 14:52 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (271 votes), past polls