Subject: Re: randomid(3)
From: David Laight <firstname.lastname@example.org>
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: email@example.com