tcrt.c - plan9port - [fork] Plan 9 from user space
  HTML git clone git://src.adamsgaard.dk/plan9port
   DIR Log
   DIR Files
   DIR Refs
   DIR README
   DIR LICENSE
       ---
       tcrt.c (2073B)
       ---
            1 #include "os.h"
            2 #include <mp.h>
            3 
            4 /* chinese remainder theorem */
            5 /* */
            6 /* handbook of applied cryptography, menezes et al, 1997, pp 610 - 613 */
            7 
            8 struct CRTpre
            9 {
           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 */
           15 };
           16 
           17 /* setup crt info, returns a newly created structure */
           18 CRTpre*
           19 crtpre(int n, mpint **m)
           20 {
           21         CRTpre *crt;
           22         int i, j;
           23         mpint *u;
           24 
           25         crt = malloc(sizeof(CRTpre)+sizeof(mpint)*3*n);
           26         if(crt == nil)
           27                 sysfatal("crtpre: %r");
           28         crt->m = crt->a;
           29         crt->c = crt->a+n;
           30         crt->p = crt->c+n;
           31         crt->n = n;
           32 
           33         /* make a copy of the moduli */
           34         for(i = 0; i < n; i++)
           35                 crt->m[i] = mpcopy(m[i]);
           36 
           37         /* precompute the products */
           38         u = mpcopy(mpone);
           39         for(i = 0; i < n; i++){
           40                 mpmul(u, m[i], u);
           41                 crt->p[i] = mpcopy(u);
           42         }
           43 
           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]);
           51                 }
           52         }
           53 
           54         mpfree(u);
           55 
           56         return crt;
           57 }
           58 
           59 void
           60 crtprefree(CRTpre *crt)
           61 {
           62         int i;
           63 
           64         for(i = 0; i < crt->n; i++){
           65                 if(i != 0)
           66                         mpfree(crt->c[i]);
           67                 mpfree(crt->p[i]);
           68                 mpfree(crt->m[i]);
           69         }
           70         free(crt);
           71 }
           72 
           73 /* convert to residues, returns a newly created structure */
           74 CRTres*
           75 crtin(CRTpre *crt, mpint *x)
           76 {
           77         int i;
           78         CRTres *res;
           79 
           80         res = malloc(sizeof(CRTres)+sizeof(mpint)*crt->n);
           81         if(res == nil)
           82                 sysfatal("crtin: %r");
           83         res->n = crt->n;
           84         for(i = 0; i < res->n; i++){
           85                 res->r[i] = mpnew(0);
           86                 mpmod(x, crt->m[i], res->r[i]);
           87         }
           88         return res;
           89 }
           90 
           91 /* garners algorithm for converting residue form to linear */
           92 void
           93 crtout(CRTpre *crt, CRTres *res, mpint *x)
           94 {
           95         mpint *u;
           96         int i;
           97 
           98         u = mpnew(0);
           99         mpassign(res->r[0], x);
          100 
          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);
          106                 mpadd(x, u, x);
          107         }
          108 
          109         mpfree(u);
          110 }
          111 
          112 /* free the residue */
          113 void
          114 crtresfree(CRTres *res)
          115 {
          116         int i;
          117 
          118         for(i = 0; i < res->n; i++)
          119                 mpfree(res->r[i]);
          120         free(res);
          121 }