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