Search

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);
}