X-Git-Url: https://git.distorted.org.uk/~mdw/catacomb-python/blobdiff_plain/7de4d3febf0dd39eac67ed682ee9e0083fed2db7..f77c6b68327aac736a5bb8098ae37df86ae6a5d4:/pock.1

diff --git a/pock.1 b/pock.1
index 22dab5c..6879bc5 100644
--- a/pock.1
+++ b/pock.1
@@ -157,14 +157,34 @@ and often they must pessimistically assume
 that the number was chosen maliciously,
 and the worst-case
 .IR n /4
-bound is the best one can do.
+bound is the best one can do using the Rabin\(enMiller test.
 For large candidates,
 this is inconveniently slow.
 (Also, many implementations incorrectly use
 a number of iterations suitable for randomly chosen primes
 for testing candidates of unknown provenance.)
 .PP
-The
+There
+.I are
+stronger probabilistic tests.
+A combination of Rabin\(enMiller and
+Grantham's Frobenius test
+is known as the
+Baillie\(enPSW test
+(after Baillie, Pomerance, Selfridge, and Wagstaff);
+there are
+.I no
+known composites which pass this test,
+nor is it known how to construct any.
+On the other hand, it's been conjectured that
+infinitely many Baillie\(enPSW pseudoprimes exist.
+While it may be reasonable to assume
+the strength of the Baillie\(enPSW test,
+it must be borne in mind that this
+.I does
+constitute a security assumption.
+.PP
+By contrast,the
 .B pock
 program will generate prime numbers
 of sizes suitable for use in cryptography,
@@ -452,7 +472,7 @@ the order of
 in
 .RB ( Z /\fIp Z )\*(ss\(**\*(se
 divides
-.I p
+.I n
 \-
 1.
 Consider some prime
@@ -470,7 +490,7 @@ has order dividing
 From
 .BR 4 ,
 we have
-.IR t \*(ss q \*(se
+.I t
 \*(/=
 1
 (mod
@@ -494,9 +514,7 @@ dividing
 and,
 from
 .BR 1 ,
-the
-.I q
-are distinct,
+these primes are distinct,
 we deduce that
 .I Q
 divides
@@ -747,6 +765,13 @@ Hasse's theorem tells us that
 .RI # E\*(usp\*(ue |
 \(<=
 .RI 2\*(sr p ,
+so, in particular,
+.RI # E\*(usp\*(ue
+\-
+.I p
+\- 1
+\(<=
+.RI 2\*(sr p ,
 whence
 .I p
 + 1 +