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 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?
2017-02-08, 13:01   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20B116 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

58916 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[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(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 101110111002 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 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 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.

 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 06:49.

Fri Nov 27 06:49:20 UTC 2020 up 78 days, 4 hrs, 4 users, load averages: 0.79, 1.23, 1.23