next up previous contents index Search
Next: 0.5.7.3 References Up: 0.5.7 Addition Chaining Previous: 0.5.7.1 Source Code

0.5.7.2 Source Code


//
// Compute x^y mod n efficiently
//

unsigned long AddChain(unsigned long x, unsigned long y, unsigned long n) 
{
  unsigned long s, t, u;

  s = 1;
  t = x; 
  u = y;

  while (u)
  {

    //
    // if u is not evenly divisible by two then multiply and mod once
    //
    if (u & 1)
    {
      s = (s * t) % n;
    }    

    //
    // now, u must be divisible by two (every other number is...)
    // So, divide u by two, square t, and divide by n.
    //
    u >>= 1;    
    t = (t * t) % n;
  }

  return(s);
}

Scott Gasch
1999-07-09