1 /*
  2  *  bignum_mod.c
  3  *  BigMath
  4  *
  5  *  Created by Curtis Jones on 2007.08.05.
  6  *  Copyright 2007 __MyCompanyName__. All rights reserved.
  7  *
  8  */
  9 
 10 #include "bignum.h"
 11 
 12 bignum_t *
 13 bignum_mod (bignum_t *rmdr, bignum_t *divd, bignum_t *divs)
 14 {
 15   bignum_div(NULL, rmdr, divd, divs);
 16   
 17   return rmdr;
 18 }
 19 
 20 #define BIGNUM_TIMEDIF(tv1,tv2) ( \
 21   tv1.tv_usec > tv2.tv_usec ? \
 22     (((tv2.tv_sec - tv1.tv_sec) - 1.0) + ((tv2.tv_usec + (1000000 - tv1.tv_usec)) / 1000000.0)) \
 23   : \
 24     (((tv2.tv_sec - tv1.tv_sec)      ) + ((tv2.tv_usec - tv1.tv_usec) / 1000000.0)) \
 25   )
 26 
 27 bignum_t *
 28 bignum_modpow (bignum_t *res, bignum_t *num, bignum_t *exp, bignum_t *mod)
 29 {
 30   bignum_t *tmp  = bignum_alloc();
 31   bignum_t *_exp = bignum_alloc();
 32   bignum_t *_num = bignum_alloc();
 33   
 34   bignum_set(res,  1);        // result = 1
 35   bignum_set_bn(_exp, exp);
 36   bignum_set_bn(_num, num);
 37   
 38   while ( bignum_gt(_exp,bignum_zero()) ) {
 39     if (bignum_isbitset(_exp,1)) {
 40       bignum_mul(tmp, res, _num);
 41       bignum_mod(res, tmp, mod);
 42     }
 43     
 44     bignum_rshift(_exp, 1);
 45     bignum_pow(tmp, _num, bignum_two());
 46     bignum_mod(_num, tmp, mod);
 47   }
 48   
 49   bignum_free( tmp  );
 50   bignum_free( _exp );
 51   bignum_free( _num );
 52   
 53   return res;
 54 }
 55 
 56 // a = num
 57 // b = mod
 58 // y = res
 59 // a >= b
 60 //
 61 bignum_t *
 62 bignum_modinv (bignum_t *res_d, bignum_t *res_x, bignum_t *res_y, bignum_t *num, bignum_t *mod)
 63 {
 64   bignum_t * a    = bignum_alloc();
 65   bignum_t * b    = bignum_alloc();
 66   bignum_t * x    = bignum_alloc();
 67   bignum_t * x1   = bignum_alloc();
 68   bignum_t * x2   = bignum_alloc();
 69   bignum_t * r    = bignum_alloc();
 70   bignum_t * y    = bignum_alloc();
 71   bignum_t * y1   = bignum_alloc();
 72   bignum_t * y2   = bignum_alloc();
 73   bignum_t * q    = bignum_alloc();
 74   bignum_t * d    = bignum_alloc();
 75   bignum_t * tmp1 = bignum_alloc();
 76   
 77   bignum_set_bn(a, num);
 78   bignum_set_bn(b, mod);
 79   
 80   if (res_d != NULL) __bignum_zero( res_d );
 81   if (res_x != NULL) __bignum_zero( res_x );
 82   if (res_y != NULL) __bignum_zero( res_y );
 83   
 84   // if b == 0, then y = 0; nothing more to do
 85   //
 86   if (bignum_iszero(b))
 87     goto bail;
 88   
 89   bignum_set(x2, 1);
 90   bignum_set(x1, 0);
 91   bignum_set(y2, 0);
 92   bignum_set(y1, 1);
 93   
 94   while (bignum_gt(b,bignum_zero()))
 95   {
 96     bignum_div(q, NULL, a, b);          // q = a / b
 97     
 98     bignum_mul(tmp1, q, b);             // tmp1 = q * b
 99     bignum_sub(r, a, tmp1);             // r = a - tmp1
100     
101     bignum_mul(tmp1, q, x1);            // tmp1 = q * x1
102     bignum_sub(x, x2, tmp1);            // x = x2 - tmp1
103     
104     bignum_mul(tmp1, q, y1);            // tmp1 = q * y1
105     bignum_sub(y, y2, tmp1);            // y = y2 - tmp1
106     
107     bignum_set_bn(a,  b );
108     bignum_set_bn(b,  r );
109     bignum_set_bn(x2, x1);
110     bignum_set_bn(x1, x );
111     bignum_set_bn(y2, y1);
112     bignum_set_bn(y1, y );
113   }
114   
115   bignum_set_bn(d, a );
116   bignum_set_bn(x, x2);
117   bignum_set_bn(y, y2);
118   
119 bail:
120   if (res_d != NULL) bignum_set_bn(res_d, a);
121   if (res_x != NULL) bignum_set_bn(res_x, x2);
122   if (res_y != NULL) bignum_set_bn(res_y, y2);
123   
124   bignum_free( a    );
125   bignum_free( b    );
126   bignum_free( x    );
127   bignum_free( x1   );
128   bignum_free( x2   );
129   bignum_free( r    );
130   bignum_free( y    );
131   bignum_free( y1   );
132   bignum_free( y2   );
133   bignum_free( q    );
134   bignum_free( d    );
135   bignum_free( tmp1 );
136   
137   return res_y;
138 }


syntax highlighted by Code2HTML, v. 0.9.1