2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ implement the gcd>1 version, then I might be impressed. $\endgroup$ – Roddy MacPhee Aug 15 at 16:25
  • $\begingroup$ @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. $\endgroup$ – Mendi Barel Aug 15 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.