/* 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.hallecks.c.html
© Copyright 2003 by John Halleck, All Rights Reserved.
This snapshot was last modified on January 12th, 2009
And the underlying file was last modified on December 12th, 2005