1 files changed, 32 insertions, 27 deletions

diff --git a/libsec/port/probably_prime.c b/libsec/port/probably_prime.c
index 4eaccbad..93fdebf0 100644
--- a/libsec/port/probably_prime.c
+++ b/libsec/port/probably_prime.c
@@ -9,7 +9,7 @@
 int
 probably_prime(mpint *n, int nrep)
 {
-	int j, k, rep, nbits, isprime = 1;
+	int j, k, rep, nbits, isprime;
 	mpint *nm1, *q, *x, *y, *r;
 
 	if(n->sign < 0)
@@ -19,18 +19,18 @@ probably_prime(mpint *n, int nrep)
 		nrep = 18;
 
 	k = mptoi(n);
-	if(k == 2)		// 2 is prime
+	if(k == 2) 	      /* 2 is prime */
 		return 1;
-	if(k < 2)		// 1 is not prime
+	if(k < 2) 	       /* 1 is not prime */
 		return 0;
-	if((n->p[0] & 1) == 0)	// even is not prime
+	if((n->p[0] & 1) == 0)  /* even is not prime */
 		return 0;
 
-	// test against small prime numbers
+	/* test against small prime numbers */
 	if(smallprimetest(n) < 0)
 		return 0;
 
-	// fermat test, 2^n mod n == 2 if p is prime
+	/* fermat test, 2^n mod n == 2 if p is prime */
 	x = uitomp(2, nil);
 	y = mpnew(0);
 	mpexp(x, n, n, y);
@@ -43,38 +43,43 @@ probably_prime(mpint *n, int nrep)
 
 	nbits = mpsignif(n);
 	nm1 = mpnew(nbits);
-	mpsub(n, mpone, nm1);	// nm1 = n - 1 */
+	mpsub(n, mpone, nm1);   /* nm1 = n - 1 */
 	k = mplowbits0(nm1);
 	q = mpnew(0);
-	mpright(nm1, k, q);	// q = (n-1)/2**k
+	mpright(nm1, k, q);     /* q = (n-1)/2**k */
 
 	for(rep = 0; rep < nrep; rep++){
-		
-		// x = random in [2, n-2]
-		r = mprand(nbits, prng, nil);
-		mpmod(r, nm1, x);
-		mpfree(r);
-		if(mpcmp(x, mpone) <= 0)
-			continue;
+		for(;;){
+			/* find x = random in [2, n-2] */
+			r = mprand(nbits, prng, nil);
+			mpmod(r, nm1, x);
+			mpfree(r);
+			if(mpcmp(x, mpone) > 0)
+				break;
+		}
 
-		// y = x**q mod n
+		/* y = x**q mod n */
 		mpexp(x, q, n, y);
 
 		if(mpcmp(y, mpone) == 0 || mpcmp(y, nm1) == 0)
-			goto done;
+		 	continue;
 
-		for(j = 1; j < k; j++){
-			mpmul(y, y, x);
-			mpmod(x, n, y);	// y = y*y mod n
-			if(mpcmp(y, nm1) == 0)
-				goto done;
-			if(mpcmp(y, mpone) == 0){
-				isprime = 0;
-				goto done;
-			}
+		for(j = 1;; j++){
+		 	if(j >= k) {
+		 		isprime = 0;
+		 		goto done;
+		 	}
+		 	mpmul(y, y, x);
+		 	mpmod(x, n, y); /* y = y*y mod n */
+		 	if(mpcmp(y, nm1) == 0)
+		 		break;
+		 	if(mpcmp(y, mpone) == 0){
+		 		isprime = 0;
+		 		goto done;
+		 	}
 		}
-		isprime = 0;
 	}
+	isprime = 1;
 done:
 	mpfree(y);
 	mpfree(x);