Found a new way to do CRT on prime vector

79 Views Asked by At

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?