libmp: add mpfield() function for fast field arithmetic

instead of testing for special field primes each time in mpmod(),
make it explicit with a mpfiled() function that tests a modulus N
to be of some special form that can be reduced more efficiently with
some precalculation, and replaces N with a Mfield* when it can. the
Mfield*'s are recognized by mpmod() as they have the MPfield flag
set and provide a function pointer that executes the fast reduction.

1 files changed, 9 insertions, 11 deletions

diff --git a/sys/src/libmp/port/mpexp.c b/sys/src/libmp/port/mpexp.c
index 534fb33a9..f5d7ac94d 100644
--- a/sys/src/libmp/port/mpexp.c
+++ b/sys/src/libmp/port/mpexp.c
@@ -61,25 +61,23 @@ mpexp(mpint *b, mpint *e, mpint *m, mpint *res)
 	j = 0;
 	for(;;){
 		for(; bit != 0; bit >>= 1){
-			mpmul(t[j], t[j], t[j^1]);
-			if(bit & d)
-				mpmul(t[j^1], b, t[j]);
+			if(m != nil)
+				mpmodmul(t[j], t[j], m, t[j^1]);
 			else
+				mpmul(t[j], t[j], t[j^1]);
+			if(bit & d) {
+				if(m != nil)
+					mpmodmul(t[j^1], b, m, t[j]);
+				else
+					mpmul(t[j^1], b, t[j]);
+			} else
 				j ^= 1;
-			if(m != nil && t[j]->top > m->top){
-				mpmod(t[j], m, t[j^1]);
-				j ^= 1;
-			}
 		}
 		if(--i < 0)
 			break;
 		bit = mpdighi;
 		d = e->p[i];
 	}
-	if(m != nil){
-		mpmod(t[j], m, t[j^1]);
-		j ^= 1;
-	}
 	if(t[j] == res){
 		mpfree(t[j^1]);
 	} else {