 mersenneforum.org Complexity of Chinese Remainder Theorem
 Register FAQ Search Today's Posts Mark Forums Read 2017-02-08, 10:12 #1 carpetpool   "Sam" Nov 2016 5×67 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?   2017-02-08, 13:01   #2
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts Quote:
 Originally Posted by carpetpool 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?
Code:
my(a=primes([2,38677]),b=vector(#a,i,Mod(random(a[i]-1),a[i])));fold((x,y)->chinese(x,y),b)
runs in 782 ms. on my machine roughly and
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)
is 3,970 ms.

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)
is about 19,470 ms. and this includes generating the primes etc. so roughly speaking every time you double the top prime used you times by 5 the time needed. okay the ratio seems to start falling more the higher you go for me personally. 38677 *8 gave a time of about 1 min, 30.172 seconds , note I haven't done too much testing at each level to get a random sample.   2017-02-08, 15:37   #3
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

5·17·19 Posts Quote:
 Originally Posted by science_man_88 Code: my(a=primes([2,38677]),b=vector(#a,i,Mod(random(a[i]-1),a[i])));fold((x,y)->chinese(x,y),b) runs in 782 ms. on my machine roughly and 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) is 3,970 ms. 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) is about 19,470 ms.
You can do it much faster. It is a known problem, and solvable in almost linear time with binary splitting.

In vector v give the problem: if you need x==r[i] mod m[i] for i=1..L, then v=[Mod(r,m),...,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));
if(L==2,return(chinese(v,v)));
mid=L\2;return(chinese(f(vecextract(v,vector(mid,j,j))),f(vecextract(v,vector(L-mid,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);
it has given (in the first line the solution of the sample CRT problem)
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.   2017-02-09, 10:30 #4 Nick   Dec 2012 The Netherlands 33·67 Posts If you are interested in the theory, look up Garner's algorithm in Prof. Knuth's "The Art of Computer Programming" (volume 2).   2017-02-09, 19:26 #5 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 32·101 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 non-GMP 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 Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post alpertron Math 23 2017-12-15 16:46 Nick Number Theory Discussion Group 4 2016-10-31 22:26 ShiningArcanine Math 2 2007-11-17 10:01 ShiningArcanine Software 3 2007-11-17 05:55 TheJudger Math 4 2007-10-18 19:01

All times are UTC. The time now is 03:05.

Tue Feb 7 03:05:39 UTC 2023 up 173 days, 34 mins, 1 user, load averages: 1.12, 1.15, 1.11