Use is_pseudoprime instead of is_prime in bn_bpsw.c

This is more accurate and improves readability a bit. Apart from a comment
tweak this is sed + knfmt (which resulted in four wrapped lines).

Discussed with beck and jsing

1 files changed, 33 insertions, 30 deletions

diff --git a/lib/libcrypto/bn/bn_bpsw.c b/lib/libcrypto/bn/bn_bpsw.c
index a1acbbf1e98..82a4e871461 100644
--- a/lib/libcrypto/bn/bn_bpsw.c
+++ b/lib/libcrypto/bn/bn_bpsw.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: bn_bpsw.c,v 1.9 2023/05/10 12:21:55 tb Exp $ */
+/*	$OpenBSD: bn_bpsw.c,v 1.10 2023/05/10 21:05:24 tb Exp $ */
 /*
  * Copyright (c) 2022 Martin Grenouilloux <martin.grenouilloux@lse.epita.fr>
  * Copyright (c) 2022 Theo Buehler <tb@openbsd.org>
@@ -156,7 +156,7 @@ bn_lucas(BIGNUM *U, BIGNUM *V, const BIGNUM *k, const BIGNUM *D,
  */
 
 static int
-bn_strong_lucas_test(int *is_prime, const BIGNUM *n, const BIGNUM *D,
+bn_strong_lucas_test(int *is_pseudoprime, const BIGNUM *n, const BIGNUM *D,
     BN_CTX *ctx)
 {
 	BIGNUM *k, *U, *V;
@@ -194,7 +194,7 @@ bn_strong_lucas_test(int *is_prime, const BIGNUM *n, const BIGNUM *D,
 		goto err;
 
 	if (BN_is_zero(U) || BN_is_zero(V)) {
-		*is_prime = 1;
+		*is_pseudoprime = 1;
 		goto done;
 	}
 
@@ -208,7 +208,7 @@ bn_strong_lucas_test(int *is_prime, const BIGNUM *n, const BIGNUM *D,
 			goto err;
 
 		if (BN_is_zero(V)) {
-			*is_prime = 1;
+			*is_pseudoprime = 1;
 			goto done;
 		}
 	}
@@ -217,7 +217,7 @@ bn_strong_lucas_test(int *is_prime, const BIGNUM *n, const BIGNUM *D,
 	 * If we got here, n is definitely composite.
 	 */
 
-	*is_prime = 0;
+	*is_pseudoprime = 0;
 
  done:
 	ret = 1;
@@ -235,7 +235,7 @@ bn_strong_lucas_test(int *is_prime, const BIGNUM *n, const BIGNUM *D,
  */
 
 static int
-bn_strong_lucas_selfridge(int *is_prime, const BIGNUM *n, BN_CTX *ctx)
+bn_strong_lucas_selfridge(int *is_pseudoprime, const BIGNUM *n, BN_CTX *ctx)
 {
 	BIGNUM *D, *two;
 	int is_perfect_square, jacobi_symbol, sign;
@@ -247,7 +247,7 @@ bn_strong_lucas_selfridge(int *is_prime, const BIGNUM *n, BN_CTX *ctx)
 	if (!bn_is_perfect_square(&is_perfect_square, n, ctx))
 		goto err;
 	if (is_perfect_square) {
-		*is_prime = 0;
+		*is_pseudoprime = 0;
 		goto done;
 	}
 
@@ -278,7 +278,7 @@ bn_strong_lucas_selfridge(int *is_prime, const BIGNUM *n, BN_CTX *ctx)
 
 		/* n and D have prime factors in common. */
 		if (jacobi_symbol == 0) {
-			*is_prime = 0;
+			*is_pseudoprime = 0;
 			goto done;
 		}
 
@@ -288,7 +288,7 @@ bn_strong_lucas_selfridge(int *is_prime, const BIGNUM *n, BN_CTX *ctx)
 		BN_set_negative(D, sign == -1);
 	}
 
-	if (!bn_strong_lucas_test(is_prime, n, D, ctx))
+	if (!bn_strong_lucas_test(is_pseudoprime, n, D, ctx))
 		goto err;
 
  done:
@@ -318,7 +318,7 @@ bn_strong_lucas_selfridge(int *is_prime, const BIGNUM *n, BN_CTX *ctx)
  */
 
 static int
-bn_fermat(int *is_prime, const BIGNUM *n, const BIGNUM *n_minus_one,
+bn_fermat(int *is_pseudoprime, const BIGNUM *n, const BIGNUM *n_minus_one,
     const BIGNUM *k, int s, const BIGNUM *base, BN_CTX *ctx, BN_MONT_CTX *mctx)
 {
 	BIGNUM *power;
@@ -338,7 +338,7 @@ bn_fermat(int *is_prime, const BIGNUM *n, const BIGNUM *n_minus_one,
 		goto err;
 
 	if (BN_is_one(power) || BN_cmp(power, n_minus_one) == 0) {
-		*is_prime = 1;
+		*is_pseudoprime = 1;
 		goto done;
 	}
 
@@ -349,13 +349,13 @@ bn_fermat(int *is_prime, const BIGNUM *n, const BIGNUM *n_minus_one,
 
 		/* n is a pseudoprime for base. */
 		if (BN_cmp(power, n_minus_one) == 0) {
-			*is_prime = 1;
+			*is_pseudoprime = 1;
 			goto done;
 		}
 
 		/* n is composite: there's a square root of unity != 1 or -1. */
 		if (BN_is_one(power)) {
-			*is_prime = 0;
+			*is_pseudoprime = 0;
 			goto done;
 		}
 	}
@@ -364,7 +364,7 @@ bn_fermat(int *is_prime, const BIGNUM *n, const BIGNUM *n_minus_one,
 	 * If we get here, n is definitely composite: base^(n-1) != 1.
 	 */
 
-	*is_prime = 0;
+	*is_pseudoprime = 0;
 
  done:
 	ret = 1;
@@ -377,11 +377,12 @@ bn_fermat(int *is_prime, const BIGNUM *n, const BIGNUM *n_minus_one,
 
 /*
  * Miller-Rabin primality test for base 2 and for |rounds| of random bases.
- * On success: is_prime == 0 implies n is composite - the converse is false.
+ * On success: is_pseudoprime == 0 implies that n is composite.
  */
 
 static int
-bn_miller_rabin(int *is_prime, const BIGNUM *n, BN_CTX *ctx, size_t rounds)
+bn_miller_rabin(int *is_pseudoprime, const BIGNUM *n, BN_CTX *ctx,
+    size_t rounds)
 {
 	BN_MONT_CTX *mctx = NULL;
 	BIGNUM *base, *k, *n_minus_one, *three;
@@ -401,12 +402,12 @@ bn_miller_rabin(int *is_prime, const BIGNUM *n, BN_CTX *ctx, size_t rounds)
 		goto err;
 
 	if (BN_is_word(n, 2) || BN_is_word(n, 3)) {
-		*is_prime = 1;
+		*is_pseudoprime = 1;
 		goto done;
 	}
 
 	if (BN_cmp(n, BN_value_one()) <= 0 || !BN_is_odd(n)) {
-		*is_prime = 0;
+		*is_pseudoprime = 0;
 		goto done;
 	}
 
@@ -440,9 +441,9 @@ bn_miller_rabin(int *is_prime, const BIGNUM *n, BN_CTX *ctx, size_t rounds)
 	if (!BN_set_word(base, 2))
 		goto err;
 
-	if (!bn_fermat(is_prime, n, n_minus_one, k, s, base, ctx, mctx))
+	if (!bn_fermat(is_pseudoprime, n, n_minus_one, k, s, base, ctx, mctx))
 		goto err;
-	if (!*is_prime)
+	if (!*is_pseudoprime)
 		goto done;
 
 	/*
@@ -457,9 +458,10 @@ bn_miller_rabin(int *is_prime, const BIGNUM *n, BN_CTX *ctx, size_t rounds)
 		if (!bn_rand_interval(base, three, n_minus_one))
 			goto err;
 
-		if (!bn_fermat(is_prime, n, n_minus_one, k, s, base, ctx, mctx))
+		if (!bn_fermat(is_pseudoprime, n, n_minus_one, k, s, base, ctx,
+		    mctx))
 			goto err;
-		if (!*is_prime)
+		if (!*is_pseudoprime)
 			goto done;
 	}
 
@@ -467,7 +469,7 @@ bn_miller_rabin(int *is_prime, const BIGNUM *n, BN_CTX *ctx, size_t rounds)
 	 * If we got here, we have a Miller-Rabin pseudoprime.
 	 */
 
-	*is_prime = 1;
+	*is_pseudoprime = 1;
 
  done:
 	ret = 1;
@@ -485,7 +487,8 @@ bn_miller_rabin(int *is_prime, const BIGNUM *n, BN_CTX *ctx, size_t rounds)
  */
 
 int
-bn_is_prime_bpsw(int *is_prime, const BIGNUM *n, BN_CTX *in_ctx, size_t rounds)
+bn_is_prime_bpsw(int *is_pseudoprime, const BIGNUM *n, BN_CTX *in_ctx,
+    size_t rounds)
 {
 	BN_CTX *ctx = NULL;
 	BN_ULONG mod;
@@ -493,12 +496,12 @@ bn_is_prime_bpsw(int *is_prime, const BIGNUM *n, BN_CTX *in_ctx, size_t rounds)
 	int ret = 0;
 
 	if (BN_is_word(n, 2)) {
-		*is_prime = 1;
+		*is_pseudoprime = 1;
 		goto done;
 	}
 
 	if (BN_cmp(n, BN_value_one()) <= 0 || !BN_is_odd(n)) {
-		*is_prime = 0;
+		*is_pseudoprime = 0;
 		goto done;
 	}
 
@@ -507,7 +510,7 @@ bn_is_prime_bpsw(int *is_prime, const BIGNUM *n, BN_CTX *in_ctx, size_t rounds)
 		if ((mod = BN_mod_word(n, primes[i])) == (BN_ULONG)-1)
 			goto err;
 		if (mod == 0) {
-			*is_prime = BN_is_word(n, primes[i]);
+			*is_pseudoprime = BN_is_word(n, primes[i]);
 			goto done;
 		}
 	}
@@ -517,12 +520,12 @@ bn_is_prime_bpsw(int *is_prime, const BIGNUM *n, BN_CTX *in_ctx, size_t rounds)
 	if (ctx == NULL)
 		goto err;
 
-	if (!bn_miller_rabin(is_prime, n, ctx, rounds))
+	if (!bn_miller_rabin(is_pseudoprime, n, ctx, rounds))
 		goto err;
-	if (!*is_prime)
+	if (!*is_pseudoprime)
 		goto done;
 
-	if (!bn_strong_lucas_selfridge(is_prime, n, ctx))
+	if (!bn_strong_lucas_selfridge(is_pseudoprime, n, ctx))
 		goto err;
 
  done: