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;
}
[download]

Edit: 2001-03-03 by neshura