At 06:19 AM 7/8/99 -0400, Lucas Wiman wrote:
>In the book _Primes and Programming_ Head's method of multiplying
>two numbers mod n is mentioned. Is this actually more effiecient
>than simply multiplying the two numbers and taking the modulus?
No it is actually much less efficient, but you are missing
the point. In his book Peter Giblin explains why on P93.
Essentially if a and b are say 62-bit integers, to compute
a * b (mod m)
you generate intermediate values that are up to 124-bits long
which are not generally supported in Basic/Pascal/C/C++. One
would have to resort to Ubasic or a Large Integer Package.
The beauty of Head's algorithm is that it allows you to compute
the modular product using only or two extra bits. The example
in the book would allow you to compute the modular product of two
62-bit integers without intermediate values exceeding 64-bits.
As far as I know most Mersenne factoring programs use on some form
of Large Integer Package (LIP) to handle the size of numbers involved.
Regards
Alan Powell
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
