1 /*
2 * bignum_pow.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 // Knuth 4.6.3 - Algorithm A
13 //
14 bignum_t *
15 bignum_pow (bignum_t *Y, bignum_t *num, bignum_t *exp)
16 {
17 bignum_t *N = bignum_alloc();
18 bignum_t *Z = bignum_alloc();
19 bignum_t *t = bignum_alloc();
20 bignum_t *x = bignum_alloc();
21 bignum_t *w = bignum_alloc();
22
23 bignum_set_bn(N, exp);
24 bignum_set(Y, 1);
25 bignum_set_bn(Z, num);
26 bignum_set(w, 2);
27
28 while (1) {
29 bignum_mod(t, N, w); // t = N % w
30 bignum_div(x, NULL, N, w); // x = N / w
31 bignum_set_bn(N, x); // N = x
32
33 if (!bignum_iszero(t)) {
34 bignum_mul(x, Z, Y); // x = Z * Y
35 bignum_set_bn(Y, x); // Y = x
36
37 if (bignum_iszero(N)) // N == 0
38 break;
39 }
40
41 bignum_mul(x, Z, Z); // x = Z * Z
42 bignum_set_bn(Z, x); // Z = x
43 }
44
45 bignum_free( N );
46 bignum_free( Z );
47 bignum_free( t );
48 bignum_free( x );
49 bignum_free( w );
50
51 return Y;
52 }
syntax highlighted by Code2HTML, v. 0.9.1