A probabilistic primality test filters large random candidates before asymmetric key generation. Random bytes become a bignum; composite candidates are discarded, and candidates that pass are used as probable primes. section 8.2.2
Exact factorization can test primality by checking divisors through √N, but that approach becomes impractical for numbers such as 1,024-bit candidates. Probabilistic tests instead sample bases a and check prime-number properties, including Fermat-style congruences such as a^(p−1) ≡ 1 mod p. section 8.2.2
The operational flow is:
- Generate random bytes of the required length and interpret them as a candidate integer. section 8.2.2
- Test the candidate with selected random bases or trials. section 8.2.2
- Reject composites and repeat generation until a candidate passes for key generation. section 8.2.2
Figure 8.5 Prime numbers are generated by testing random numbers for primality.
Trace candidate generation through the primality filter to asymmetric-key construction. section 8.2.2
Equation 8.3
\[\begin{aligned} \label{equation:fermats-little-theorem-1} \begin{aligned} a^p &= a \pmod{p} \\ a^p - a &= 0 \pmod{p} \\ (a)(a^{p-1} - 1) &= 0 \pmod{p} \\ \end{aligned} \end{aligned}\]Inspect the modular relation underlying the Fermat-style primality check. section 8.2.2
