E. Mayer wrote:
[EMAIL PROTECTED] writes:
Anyone see any benefit in this in terms of comparable cost of
implementation vs. pure multiprecision division?
None of the high-quality trial-factoring codes use anything remotely resembling
direct multiprecision division - one typically does modular binary exponentiation
to get a^b mod n, with the individual modmuls using a very fast divideless modulo,
typically of either the Barrett or Montgomery variety. Crandall & Pomerance's
book is a good reference for this kind of thing.
Cheers,
-Ernst
Ernst,
Thanks for the constructive response, it looks like Crandall &
Pomerance's book is a wonderful thing.
I'm looking over the Barrett and Montgomery algorithms now and will
check out the MPrime source as soon as I feel comfortable w/ B&M algos.
--jim
_______________________________________________
Prime mailing list
[email protected]
http://hogranch.com/mailman/listinfo/prime
