Subject: Re: randomid(3)
To: <>
From: David Laight <>
List: tech-userlevel
Date: 09/11/2003 08:33:02
> > The 'fast modular exponentiation' routine isn't particularly fast!
> > That function can easily be written without a single divide (for the
> > values of 'mod' in that routine).
> 	send code.

Use the equality:
	(a * k + b) mod n = (a * (k - n) + b) mod n
and pick k as the first power of 2 above n.
(usefully all the 'n' are just below a power of 2)

This is the equality you use when you calculate the remainder
when a decimal number is divided by 9 by summing its digits.


David Laight: