20170208, 10:12  #1 
"Sam"
Nov 2016
2×3×53 Posts 
Complexity of Chinese Remainder Theorem
What is the average running time on the Chinese remainder theorem for solving congruence modulo primes up to p_n where p_n is the nth prime?
e.g. the complexity of solving congruence set {[x, 2], [x_2, 3}, {[x, 2], [x_2, 3], [x_3, 5]}, {[x, 2], [x_2, 3], [x_3, 5], [x_4, 7]},.... {[x, 2], [x_2, 3], [x_3, 5], [x_4, 7]......, [x_n, p_n]} For the purpose of generating fairy large random numbers, what is the complexity at solving congruence sets modulo the first n primes? Programs such as ntheory, PARI/GP should handle this but I'm unaware of the timing. It takes a few seconds for primes p < 1669, but what about timing when solving congruence sets mod primes p < 38677? 
20170208, 13:01  #2  
"Forget I exist"
Jul 2009
Dumbassville
20B1_{16} Posts 
Quote:
Code:
my(a=primes([2,38677]),b=vector(#a,i,Mod(random(a[i]1),a[i])));fold((x,y)>chinese(x,y),b) Code:
my(a=primes([2,38677*2]),b=vector(#a,i,Mod(random(a[i]1),a[i])));fold((x,y)>chinese(x,y),b) and Code:
my(a=primes([2,38677*4]),b=vector(#a,i,Mod(random(a[i]1),a[i])));fold((x,y)>chinese(x,y),b) Last fiddled with by science_man_88 on 20170208 at 13:07 Reason: adding more information. 

20170208, 15:37  #3  
"Robert Gerbicz"
Oct 2005
Hungary
589_{16} Posts 
Quote:
In vector v give the problem: if you need x==r[i] mod m[i] for i=1..L, then v=[Mod(r[1],m[1]),...,Mod(r[L],m[L])]. The solution (if exists) will be f(v), note that this solves the general problem, so we don't assume that the m[] values are pairwise coprime. Code:
allocatemem(10^9) default(primelimit,10^7) f(v)={local(L,mid,j);L=length(v); if(L==1,return(v[1])); if(L==2,return(chinese(v[1],v[2]))); mid=L\2;return(chinese(f(vecextract(v,vector(mid,j,j))),f(vecextract(v,vector(Lmid,j,mid+j)))))} v=[Mod(0,2),Mod(1,3),Mod(4,5),Mod(2,7)]; f(v) test(s)={a=primes([2,s]);b=vector(#a,i,Mod(random(a[i]),a[i]));return(f(b))} # test(38677); test(2*38677); test(4*38677); test(8*38677); test(16*38677); test(32*38677); test(64*38677); test(128*38677); test(256*38677); Code:
? %4 = Mod(184, 210) ? time = 11 ms. ? time = 23 ms. ? time = 51 ms. ? time = 113 ms. ? time = 267 ms. ? time = 646 ms. ? time = 1,533 ms. ? time = 3,736 ms. ? time = 8,924 ms. 

20170209, 10:30  #4 
Dec 2012
The Netherlands
10111011100_{2} Posts 
If you are interested in the theory, look up Garner's algorithm in Prof. Knuth's "The Art of Computer Programming" (volume 2).

20170209, 19:26  #5 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2·3·151 Posts 
Since Perl/ntheory was mentioned... The GMP code for my chinese function does a recursive function to what Robert mentions, though I chunk by splitting in 8 rather than 2. The times for large numbers of inputs are nearly identical to his simple test function on my machine.
But ... my nonGMP chinese function takes surprisingly long to return indicating overflow. It comes down to, of all things, sorting the moduli. I just fixed that. It now goes to GMP with little overhead even with hundreds of thousands of pairs. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Sorting on chinese remainder theorem  alpertron  Math  23  20171215 16:46 
Basic Number Theory 6: functions and the Chinese Remainder Theorem  Nick  Number Theory Discussion Group  4  20161031 22:26 
Chinese Remainder Problem  ShiningArcanine  Math  2  20071117 10:01 
Implementing Chinese Remainder Theorem in C  ShiningArcanine  Software  3  20071117 05:55 
division/remainder algorithm (trial factoring)  TheJudger  Math  4  20071018 19:01 