#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 structureCRTpre*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;		} voidcrtprefree(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 structureCRTres*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 linearvoidcrtout(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 residuevoidcrtresfree(CRTres *res){	int i; 	for(i = 0; i < res->n; i++)		mpfree(res->r[i]);	free(res);}