Complexity of Chinese Remainder Theorem

carpetpool · 2017-02-08, 10:12

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?

science_man_88 · 2017-02-08, 13:01

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.

R. Gerbicz · 2017-02-08, 15:37

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.

Nick · 2017-02-09, 10:30

If you are interested in the theory, look up Garner's algorithm in Prof. Knuth's "The Art of Computer Programming" (volume 2).

danaj · 2017-02-09, 19:26

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.

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?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Sorting on chinese remainder theorem	alpertron	Math	23	2017-12-15 16:46
Basic Number Theory 6: functions and the Chinese Remainder Theorem	Nick	Number Theory Discussion Group	4	2016-10-31 22:26
Chinese Remainder Problem	ShiningArcanine	Math	2	2007-11-17 10:01
Implementing Chinese Remainder Theorem in C	ShiningArcanine	Software	3	2007-11-17 05:55
division/remainder algorithm (trial factoring)	TheJudger	Math	4	2007-10-18 19:01

2017-02-09, 10:30	#4
Nick Dec 2012 The Netherlands 3³·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 3²·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.