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)
% Copyright 2019, Mendi Barel, All rights reserved.
% 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?