5 // chinese remainder theorem
7 // handbook of applied cryptography, menezes et al, 1997, pp 610 - 613
11 int n; // number of moduli
12 mpint **m; // pointer to moduli
13 mpint **c; // precomputed coefficients
14 mpint **p; // precomputed products
15 mpint *a[1]; // local storage
18 // setup crt info, returns a newly created structure
20 crtpre(int n, mpint **m)
26 crt = malloc(sizeof(CRTpre)+sizeof(mpint)*3*n);
28 sysfatal("crtpre: %r");
34 // make a copy of the moduli
35 for(i = 0; i < n; i++)
36 crt->m[i] = mpcopy(m[i]);
38 // precompute the products
40 for(i = 0; i < n; i++){
42 crt->p[i] = mpcopy(u);
45 // precompute the coefficients
46 for(i = 1; i < n; i++){
47 crt->c[i] = mpcopy(mpone);
48 for(j = 0; j < i; j++){
49 mpinvert(m[j], m[i], u);
50 mpmul(u, crt->c[i], u);
51 mpmod(u, m[i], crt->c[i]);
61 crtprefree(CRTpre *crt)
65 for(i = 0; i < crt->n; i++){
74 // convert to residues, returns a newly created structure
76 crtin(CRTpre *crt, mpint *x)
81 res = malloc(sizeof(CRTres)+sizeof(mpint)*crt->n);
83 sysfatal("crtin: %r");
85 for(i = 0; i < res->n; i++){
87 mpmod(x, crt->m[i], res->r[i]);
92 // garners algorithm for converting residue form to linear
94 crtout(CRTpre *crt, CRTres *res, mpint *x)
100 mpassign(res->r[0], x);
102 for(i = 1; i < crt->n; i++){
103 mpsub(res->r[i], x, u);
104 mpmul(u, crt->c[i], u);
105 mpmod(u, crt->m[i], u);
106 mpmul(u, crt->p[i-1], u);
115 crtresfree(CRTres *res)
119 for(i = 0; i < res->n; i++)