drawterm/libmp/crt.c

123 lines
2.0 KiB
C

#include "os.h"
#include <mp.h>
#include <libsec.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);
}