xbyymn.c:


/* Modular multiplication */
long xbyymn(x,y,n) long x,y,n; {
   /* Assume x,y non-negitive, n positive */
   long result;
   long current;

   /* form the binary constant 010000...00 */
   current = (long) ( (((unsigned long) ~0L) >> 1) &
                     ~(((unsigned long) ~0L) >> 2));
   /* Current is the current bit mask...  Only one bit
    * is ever set, so it could be a bit counter instead
    * of a mask */
 
   result = 0;
   while (current != 0) {

     /* printf ("Result = %ld, current = %ld\n", result, current); */
     result <<=1;

     if (result > n) { result -= n; }
        /* Note that this is not really a full compare.  Just
         * checking for a bit in a position greater than the
         * MSB of N is enough. */

     if (current & y) { /* Note that this is a 1 bit test...*/
       result = result + x;
       if (result > n) { result -= n; } /* see above */
     } 
     current >>= 1;

   }

   /*  *IF* the reduction checks above were done by just the
    * MSB test, it is possible for the result to be n too large
    * at this point.  The following test should be inserted:
    *     if (result > n) { result -= n; }
    *  This test should be a full compare test.
    */

   return result;
}

Go to ...


This page is http://www.cc.utah.edu/~nahaj/factoring/xbyymn.c.html
© Copyright 2003 by John Halleck, All Rights Reserved.
This snapshot was last modified on December 24th, 2013