Document recent changes in primality testing

With input from beck and jsing

1 files changed, 23 insertions, 8 deletions

diff --git a/src/lib/libcrypto/man/BN_generate_prime.3 b/src/lib/libcrypto/man/BN_generate_prime.3
index 268bc02a03..85c7349b1b 100644
--- a/src/lib/libcrypto/man/BN_generate_prime.3
+++ b/src/lib/libcrypto/man/BN_generate_prime.3
@@ -1,4 +1,4 @@
-.\" $OpenBSD: BN_generate_prime.3,v 1.22 2023/04/30 20:17:59 tb Exp $
+.\" $OpenBSD: BN_generate_prime.3,v 1.23 2023/05/11 05:45:33 tb Exp $
 .\" full merge up to: OpenSSL f987a4dd Jun 27 10:12:08 2019 +0200
 .\"
 .\" This file is a derived work.
@@ -67,7 +67,7 @@
 .\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 .\" OF THE POSSIBILITY OF SUCH DAMAGE.
 .\"
-.Dd $Mdocdate: April 30 2023 $
+.Dd $Mdocdate: May 11 2023 $
 .Dt BN_GENERATE_PRIME 3
 .Os
 .Sh NAME
@@ -81,7 +81,7 @@
 .Nm BN_GENCB_get_arg ,
 .Nm BN_GENCB_set_old
 .\" Nm BN_prime_checks_for_size is intentionally undocumented
-.\" because it is no longer used by LibreSSL.
+.\" because it should not be used outside of libcrypto.
 .Nd generate primes and test for primality
 .Sh SYNOPSIS
 .In openssl/bn.h
@@ -147,13 +147,14 @@ and
 test whether the number
 .Fa a
 is prime.
-In LibreSSL, both functions behave identically,
-use the Baillie-Pomerance-Selfridge-Wagstaff algorithm,
-and ignore the
+In LibreSSL, both functions behave identically
+and use the Baillie-Pomerance-Selfridge-Wagstaff algorithm
+combined with
 .Fa checks
-and
+Miller-Rabin rounds.
+The
 .Fa do_trial_division
-arguments.
+argument is ignored.
 .Pp
 It is unknown whether any composite number exists that the
 Baillie-PSW algorithm misclassifies as a prime.
@@ -161,6 +162,20 @@ Some suspect that there may be infinitely many such numbers,
 but not a single one is currently known.
 It is known that no such number exists below 2\(ha64.
 .Pp
+In order to reduce the likelihood of a composite number
+passing the primility tests
+.Fn BN_is_prime_fasttest_ex
+and
+.Fn BN_is_prime_ex ,
+a number of rounds of the probabilistic Miller-Rabin test is performed.
+If
+.Fa checks
+is positive, it is used as the number of rounds;
+if it is zero or the special value
+.Dv BN_prime_checks ,
+a suitable number of rounds is calculated from the bit length of
+.Fa a .
+.Pp
 If
 .Dv NULL
 is passed for the