go ahead... be a heretic 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??

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?)

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

Create A New User
Domain Nodelet?
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 wandering the Monastery: (7)
As of 2022-01-24 14:02 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
In 2022, my preferred method to securely store passwords is:

Results (64 votes). Check out past polls.

Notices?