Subversion Repositories planix.SVN

Rev

Rev 2 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 - 1 
#include "os.h"
2 
#include <mp.h>
3 
#include "dat.h"
4 
 
5 
// res = b**e
6 
//
7 
// knuth, vol 2, pp 398-400
8 
 
9 
enum {
10 
	Freeb=	0x1,
11 
	Freee=	0x2,
12 
	Freem=	0x4,
13 
};
14 
 
15 
//int expdebug;
16 
 
17 
void
18 
mpexp(mpint *b, mpint *e, mpint *m, mpint *res)
19 
{
20 
	mpint *t[2];
21 
	int tofree;
22 
	mpdigit d, bit;
23 
	int i, j;
24 
 
25 
	t[0] = mpcopy(b);
26 
	t[1] = res;
27 
 
28 
	tofree = 0;
29 
	if(res == b){
30 
		b = mpcopy(b);
31 
		tofree |= Freeb;
32 
	}
33 
	if(res == e){
34 
		e = mpcopy(e);
35 
		tofree |= Freee;
36 
	}
37 
	if(res == m){
38 
		m = mpcopy(m);
39 
		tofree |= Freem;
40 
	}
41 
 
42 
	// skip first bit
43 
	i = e->top-1;
44 
	d = e->p[i];
45 
	for(bit = mpdighi; (bit & d) == 0; bit >>= 1)
46 
		;
47 
	bit >>= 1;
48 
 
49 
	j = 0;
50 
	for(;;){
51 
		for(; bit != 0; bit >>= 1){
52 
			mpmul(t[j], t[j], t[j^1]);
53 
			if(bit & d)
54 
				mpmul(t[j^1], b, t[j]);
55 
			else
56 
				j ^= 1;
57 
			if(m != nil && t[j]->top > m->top){
58 
				mpmod(t[j], m, t[j^1]);
59 
				j ^= 1;
60 
			}
61 
		}
62 
		if(--i < 0)
63 
			break;
64 
		bit = mpdighi;
65 
		d = e->p[i];
66 
	}
67 
	if(m != nil){
68 
		mpmod(t[j], m, t[j^1]);
69 
		j ^= 1;
70 
	}
71 
	if(t[j] == res){
72 
		mpfree(t[j^1]);
73 
	} else {
74 
		mpassign(t[j], res);
75 
		mpfree(t[j]);
76 
	}
77 
 
78 
	if(tofree){
79 
		if(tofree & Freeb)
80 
			mpfree(b);
81 
		if(tofree & Freee)
82 
			mpfree(e);
83 
		if(tofree & Freem)
84 
			mpfree(m);
85 
	}
86 
}