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]

In reply to modular exponentiation with arbitrary precision binary numbers (did I say RSA?) by jhanna

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.