# Found a new way to do CRT on prime vector

I found a new way to do CRT on prime vector.

Given prime list P, and some residuals R=mod(n,P) , for example:

P=[2 3 5 7 11]
R=[1 0 3 1 9]


This matlab function will reconstruct the original number:

function [crt]=crt_mendi_clean(R,P)
% Example: n=434, P=primes(13), R=mod(n,P), [crt]=crt_mendi_clean(R,P)

crt=0; %init crt
primorilag=1; %init primorials with lag. [1 2 6 30 210...]
for i=1:length(R)
p=P(i);
r=R(i);
u=mod(crt,p);

for j=0:p-1, if mod(primorilag*j,p)==u, ju=j;  break, end, end
for j=0:p-1, if mod(primorilag*j,p)==r, jr=j;  break, end, end

v=mod(jr-ju,p);
crt=crt+primorilag*v;
primorilag=primorilag*p;
end
end


For our example: crt_mendi_clean([1 0 3 1 9],[2 3 5 7 11]) ouput: 603

The only restriction is the obvious one needed for reconstruction: n<primorial(P(end)).

Is this a new algorithm? or it is already known?

• implement the gcd>1 version, then I might be impressed. – Roddy MacPhee Aug 15 at 16:25
• @Roddy I'v done it, but i'm using 'factor' function and doing new inside loop to check that i didnt used already this factor. seems to work fine. – Mendi Barel Aug 15 at 17:22