**Subject:** Re: randomid(3)

**To:** *<>*

**From:** David Laight *<david@l8s.co.uk>*

**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
--
David Laight: david@l8s.co.uk