From 20c03f7a316f2de9f09321b46f24088b23ccb055 Mon Sep 17 00:00:00 2001
From: forsyth <forsyth@vitanuova.com>
Date: Sun, 7 Mar 2010 10:33:50 +0000
Subject: 20100307-1033

---
 libsec/port/probably_prime.c | 44 ++++++++++++++++++++++----------------------
 1 file changed, 22 insertions(+), 22 deletions(-)

(limited to 'libsec')

diff --git a/libsec/port/probably_prime.c b/libsec/port/probably_prime.c
index 93fdebf0..2e750393 100644
--- a/libsec/port/probably_prime.c
+++ b/libsec/port/probably_prime.c
@@ -2,10 +2,10 @@
 #include <mp.h>
 #include <libsec.h>
 
-// Miller-Rabin probabilistic primality testing
-//	Knuth (1981) Seminumerical Algorithms, p.379
-//	Menezes et al () Handbook, p.39
-// 0 if composite; 1 if almost surely prime, Pr(err)<1/4**nrep
+/* Miller-Rabin probabilistic primality testing */
+/*	Knuth (1981) Seminumerical Algorithms, p.379 */
+/*	Menezes et al () Handbook, p.39 */
+/* 0 if composite; 1 if almost surely prime, Pr(err)<1/4**nrep */
 int
 probably_prime(mpint *n, int nrep)
 {
@@ -19,11 +19,11 @@ 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 */
@@ -43,10 +43,10 @@ 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++){
 		for(;;){
@@ -62,21 +62,21 @@ probably_prime(mpint *n, int nrep)
 		mpexp(x, q, n, y);
 
 		if(mpcmp(y, mpone) == 0 || mpcmp(y, nm1) == 0)
-		 	continue;
+			continue;
 
 		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;
-		 	}
+			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 = 1;
-- 
cgit v1.2.3