Speeding up (n mod m) for very large fixed n and varying smaller m
I have a large fixed n (around 100,000 digits, say) and need to calculate (n mod m) for many different values of m, which are smaller (tens of digits). Is there is any preconditioning I can use, or any transformations that might be applied to speed this process up at all?

Sometimes it helps to multiply all the modulo together (M) and compute
X = n mod M then x[i] = X mod m[i] is easier. But your m[i] sound too big for this to help. 
The recursive version of the above is a 'remainder tree', and is indeed a good idea. If the product of the m's far exceeds the size of n you can do the remainder tree tree a block of m's at a time, possibly combined with the fast smallm modulo operation described [url="http://arxiv.org/pdf/1303.0328.pdf"]here[/url].

Thanks guys  will definitely investigate this approach.

Hi Jason, do you have a reference for the Remainder Tree approach?

[QUOTE=mickfrancis;425634]Hi Jason, do you have a reference for the Remainder Tree approach?[/QUOTE]
I'm not Jason but I think Bernstein is standard here: [url]https://cr.yp.to/arith/scaledmod20040820.pdf[/url] 
[QUOTE=CRGreathouse;425641]I'm not Jason but I think Bernstein is standard here:
[url]https://cr.yp.to/arith/scaledmod20040820.pdf[/url][/QUOTE] Great  thanks very much. 
Bernstein's paper is probably the best theoretical reference; remainder trees are only one of the algorithms it describes.
Msieve's NFS line sieve uses remaindertreebased batch factoring to handle the factorization of huge numbers of relatively small integers, and this lets the sieve use three large primes without the traditional overhead of doing so (code [url="http://sourceforge.net/p/msieve/code/HEAD/tree/trunk/common/batch_factor.c"]here[/url]). 
[QUOTE=jasonp;425721]Msieve's NFS line sieve uses remaindertreebased batch factoring to handle the factorization of huge numbers of relatively small integers.[/QUOTE]
Hi Jason, Do you use Bernstein's Scaled Remainder Trees? If not, have you experimented with them at all? Mick. 
It does not and I have not.

All times are UTC. The time now is 01:20. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2022, Jelsoft Enterprises Ltd.