Of course there's many optimizations which I'm sure I missed in the arbitrary precision binary add, multiply, subtract and modulo functions, but the scarey thing is that I think it works! I hope I don't get sued for posting this... Which, by the way, do you suppose this violates any patent/copyright laws?

It might be a bit slow, but I think it's linear time.

j

# my attempt at modular exponentiation with 
# arbitrary precision binary numbers
# in perl :-)
# consider this (C) 2000 John M Hanna under the GPL
sub badd { # binary add
 local($a,$b,$r,$c)=@_;
 while($a || $b) {
  $c=chop($a) + chop($b) + $c;
  if($c & 1) {
   $r="1$r";
  } else {
   $r="0$r";
  }
  $c>>=1;
 }
 $r="1$r" if $c;
 $r;
}
sub bsub { # binary subtract
 local($a,$b,$r,$c)=@_;
 while($a || $b) {
  $c=chop($a) - chop($b) - $c;
  if($c==0) {
   $r="0$r";
  } elsif($c == 1) {
   $r="1$r";
   $c=0;
  } elsif($c == -1) {
   $r="1$r";
   $c=1;
  } else {
   $r="0$r";
   $c=1;
  }
  return '' if !$a && ($b || $c);
 }
 $r=~s/^0+//;
 $r='0' unless $r;
 $r;
}
sub bmul { # binary multiply
 local($a,$b,$r,$p)=@_;
 while($a) {
  if(chop($a) eq '1') {
   $r=&badd($r,"$b$p");
  }
  $p.='0';
 }
 $r;
}
sub bmod { # binary modulo
 local($a,$m,$p,$lm,$d)=@_;
 $lm=length($m);
 while($a) {
  return $a if length($a)<$lm;
  $p=substr($a,0,$lm); $a=substr($a,$lm);
  $d=&bsub($p,$m);
  return $p if $d eq '' && $a eq '';
  unless(length($d)) {
   $p.=substr($a,0,1); $a=substr($a,1);
   $d=&bsub($p,$m);
  }
  $a="$d$a";
  $a=~s/^0+//;
 }
 '0';
}
sub bmodexp { # binary modular exponentiation
 # based on http://www.frontiernet.net/~jmb184/interests/sci.crypt/sma
+ll_num_expont.html

 local($x,$y,$m,$r)=@_;
 $r=1;
 while($y) {
  if(chop($y) eq '1') {
   $r=&bmod(&bmul($r,$x),$m);
  }
  $x=&bmod(&bmul($x,$x),$m);
 }
 return $r;
}
sub i2b { # convert integer to binary
 local($i,$r)=@_;
 while($i) {
  if($i & 1) { $r="1$r";} else {$r="0$r";}
  $i>>=1;
 }
 $r || '0';
}

# an example where I know the results
print &bmodexp(&i2b(123),&i2b(17),&i2b(3233)),"=?",&i2b(855),"\n";
print &bmodexp(&i2b(855),&i2b(2753),&i2b(3233)),"=?",&i2b(123),"\n";

[download]
  • Comment on modular exponentiation with arbitrary precision binary numbers (did I say RSA?)
  • Download Code

Replies are listed 'Best First'.
Re: modular exponentiation with arbitrary precision binary numbers (did I say RSA?)
by ton (Friar) on Feb 20, 2001 at 01:25 UTC
    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;
}

    [download]

    Edit: 2001-03-03 by neshura

[reply]
[d/l]
      I didn't test it, but it looks good. Ok, so I withdraw my unformed remarks about vectors. j
[reply]
Re: modular exponentiation with arbitrary precision binary numbers (did I say RSA?)
by rpc (Monk) on Dec 01, 2000 at 00:24 UTC
    Very cool. :)

    And I hope no one can copywrite mathematics! You would probably only run into trouble if you directly specified that this was for cryptographic purposes.

[reply]
Re: modular exponentiation with arbitrary precision binary numbers (did I say RSA?)
by swiftone (Curate) on Dec 01, 2000 at 00:28 UTC
    Two questions:
    1. why do you use local rather than my?
    2. why do you do all of this as string operators rather than the binary operators perl has?
    Update: I answered #2 myself when I looked again and saw "Arbitrary length" in the comments. #1 I'm still curious about
[reply]

      Note that Perl supports binary operations on "arbitrary length" strings so this could be done using real bits instead of '0' and '1' chars. Of course, some logic would have to be reworked since you can't append one bit to a string.

              - tye (but my friends call me "Tye")
[reply]
        Yes... But actually my target lanaguage for this is javascript. Javascript doesn't support arbitrary length binary operations.

        But with this little diddly one can potentially do browser based public key crypto without needing SSL, eg to transmit credit cards, who knows what else...

        j

[reply]
        Let's see... Can you add binary strings? Multiply them? Modulo them? ... What can you do with them? Oh, I know, AND and XOR and NOT... funny, I don't remember using any of those in my code... Oh well... Ok, so maybe you could rewrite badd and bsub to do those...
[reply]
      1) I use local because (call me a fool) I'm still running perl 4 (yes FOUR) on my windoze box. I've tried to quit... Really I have... And I know I can quit any time I want. I can. I Really Can. So just LEAVE ME ALONE!
[reply]

Back to Cool Uses for Perl