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

[ton]

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

[jhanna]

I didn't test it, but it looks good. Ok, so I withdraw my unformed remarks about vectors. j