Subversion Repositories planix.SVN

#include "os.h"
#include <mp.h>

// chinese remainder theorem
//
// handbook of applied cryptography, menezes et al, 1997, pp 610 - 613

struct CRTpre
{
        int     n;              // number of moduli
        mpint   **m;            // pointer to moduli
        mpint   **c;            // precomputed coefficients
        mpint   **p;            // precomputed products
        mpint   *a[1];          // local storage
};

// setup crt info, returns a newly created structure
CRTpre*
crtpre(int n, mpint **m)
{
        CRTpre *crt;
        int i, j;
        mpint *u;

        crt = malloc(sizeof(CRTpre)+sizeof(mpint)*3*n);
        if(crt == nil)
                sysfatal("crtpre: %r");
        crt->m = crt->a;
        crt->c = crt->a+n;
        crt->p = crt->c+n;
        crt->n = n;

        // make a copy of the moduli
        for(i = 0; i < n; i++)
                crt->m[i] = mpcopy(m[i]);

        // precompute the products
        u = mpcopy(mpone);
        for(i = 0; i < n; i++){
                mpmul(u, m[i], u);
                crt->p[i] = mpcopy(u);
        }

        // precompute the coefficients
        for(i = 1; i < n; i++){
                crt->c[i] = mpcopy(mpone);
                for(j = 0; j < i; j++){
                        mpinvert(m[j], m[i], u);
                        mpmul(u, crt->c[i], u);
                        mpmod(u, m[i], crt->c[i]);
                }
        }

        mpfree(u);

        return crt;             
}

void
crtprefree(CRTpre *crt)
{
        int i;

        for(i = 0; i < crt->n; i++){
                if(i != 0)
                        mpfree(crt->c[i]);
                mpfree(crt->p[i]);
                mpfree(crt->m[i]);
        }
        free(crt);
}

// convert to residues, returns a newly created structure
CRTres*
crtin(CRTpre *crt, mpint *x)
{
        int i;
        CRTres *res;

        res = malloc(sizeof(CRTres)+sizeof(mpint)*crt->n);
        if(res == nil)
                sysfatal("crtin: %r");
        res->n = crt->n;
        for(i = 0; i < res->n; i++){
                res->r[i] = mpnew(0);
                mpmod(x, crt->m[i], res->r[i]);
        }
        return res;
}

// garners algorithm for converting residue form to linear
void
crtout(CRTpre *crt, CRTres *res, mpint *x)
{
        mpint *u;
        int i;

        u = mpnew(0);
        mpassign(res->r[0], x);

        for(i = 1; i < crt->n; i++){
                mpsub(res->r[i], x, u);
                mpmul(u, crt->c[i], u);
                mpmod(u, crt->m[i], u);
                mpmul(u, crt->p[i-1], u);
                mpadd(x, u, x);
        }

        mpfree(u);
}

// free the residue
void
crtresfree(CRTres *res)
{
        int i;

        for(i = 0; i < res->n; i++)
                mpfree(res->r[i]);
        free(res);
}