20160208, 12:00  #1 
Apr 2014
Marlow, UK
38_{16} Posts 
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?

20160208, 12:52  #2 
Dec 2014
3×5×17 Posts 
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. 
20160208, 13:37  #3 
Tribal Bullet
Oct 2004
5·709 Posts 
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 here.

20160208, 14:13  #4 
Apr 2014
Marlow, UK
2^{3}×7 Posts 
Thanks guys  will definitely investigate this approach.

20160208, 17:40  #5 
Apr 2014
Marlow, UK
70_{8} Posts 
Hi Jason, do you have a reference for the Remainder Tree approach?

20160208, 18:12  #6  
Aug 2006
175B_{16} Posts 
Quote:
https://cr.yp.to/arith/scaledmod20040820.pdf 

20160208, 18:35  #7  
Apr 2014
Marlow, UK
2^{3}·7 Posts 
Quote:


20160209, 13:38  #8 
Tribal Bullet
Oct 2004
3545_{10} Posts 
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 here). 
20160329, 14:26  #9 
Apr 2014
Marlow, UK
2^{3}·7 Posts 

20160329, 19:00  #10 
Tribal Bullet
Oct 2004
5·709 Posts 
It does not and I have not.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Widely varying LL test speeds after reboot  TrellisCross  Information & Answers  3  20161114 14:22 
Speeding up 321  diep  Math  8  20121204 15:32 
Speeding up Mersenne hunting  m_f_h  Math  8  20070518 13:49 
Benchmarks varying FSB, Memory Latency and multiplier  S485122  Software  0  20061108 20:21 
Speeding up ECM 10x  clowns789  Software  2  20040811 03:45 