4 /* chinese remainder theorem */
6 /* handbook of applied cryptography, menezes et al, 1997, pp 610 - 613 */
10 int n; /* number of moduli */
11 mpint **m; /* pointer to moduli */
12 mpint **c; /* precomputed coefficients */
13 mpint **p; /* precomputed products */
14 mpint *a[1]; /* local storage */
17 /* setup crt info, returns a newly created structure */
19 crtpre(int n, mpint **m)
25 crt = malloc(sizeof(CRTpre)+sizeof(mpint)*3*n);
27 sysfatal("crtpre: %r");
33 /* make a copy of the moduli */
34 for(i = 0; i < n; i++)
35 crt->m[i] = mpcopy(m[i]);
37 /* precompute the products */
39 for(i = 0; i < n; i++){
41 crt->p[i] = mpcopy(u);
44 /* precompute the coefficients */
45 for(i = 1; i < n; i++){
46 crt->c[i] = mpcopy(mpone);
47 for(j = 0; j < i; j++){
48 mpinvert(m[j], m[i], u);
49 mpmul(u, crt->c[i], u);
50 mpmod(u, m[i], crt->c[i]);
60 crtprefree(CRTpre *crt)
64 for(i = 0; i < crt->n; i++){
73 /* convert to residues, returns a newly created structure */
75 crtin(CRTpre *crt, mpint *x)
80 res = malloc(sizeof(CRTres)+sizeof(mpint)*crt->n);
82 sysfatal("crtin: %r");
84 for(i = 0; i < res->n; i++){
86 mpmod(x, crt->m[i], res->r[i]);
91 /* garners algorithm for converting residue form to linear */
93 crtout(CRTpre *crt, CRTres *res, mpint *x)
99 mpassign(res->r[0], x);
101 for(i = 1; i < crt->n; i++){
102 mpsub(res->r[i], x, u);
103 mpmul(u, crt->c[i], u);
104 mpmod(u, crt->m[i], u);
105 mpmul(u, crt->p[i-1], u);
112 /* free the residue */
114 crtresfree(CRTres *res)
118 for(i = 0; i < res->n; i++)