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,
in
.RB ( Z /\fIp Z )\*(ss\(**\*(se
divides
-.I p
+.I n
\-
1.
Consider some prime
From
.BR 4 ,
we have
-.IR t \*(ss q \*(se
+.I t
\*(/=
1
(mod
and,
from
.BR 1 ,
-the
-.I q
-are distinct,
+these primes are distinct,
we deduce that
.I Q
divides
.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 +