I am writing a program to do integer factorization and have to reduce a series of numbers to a given modulus. Both the number and the modulus are bigints, say 50 to 100 digits. The number changes but the modulus is always the same. Is there some way to optimize the repeated modulus calculations, perhaps by pre-computing some partial results and storing them in a table?
+1
A:
Let your bigint library worry about optimizing operations like that.
Nathon
2010-09-15 19:44:30
The bigint library optimizes calculation of a single modulus. I need a way to reduce many numbers (thousands) all to the same modulus.
2010-09-15 19:54:37
Right, and your options are to either switch to a library that optimizes that, or accept the (trivial) overhead of an extra function parameter and a few thousand extra function calls. There's not much you can do outside the library unless your modulus is smaller than the number of numbers you have, which it sounds like it isn't.
Nathon
2010-09-15 20:25:02