Primality: Baillie-PSW

17 Dec 2021

Notes Cryptography Primality: Baillie-PSW

§ Motivation

We didn't cover this in our MATH-470 course, but I was reading the source code for the GNU MP library and saw that mpz_probab_prime_p() uses Baillie-PSW^[1] on top of Miller-Rabin when checking if $n$ is a probable prime; so, I decided to learn more about it.

We've previously looked at the Miller-Rabin primality test which is a Fermat test, however, there exists strong pseudoprimes that pass Fermat tests against many bases; e.g. there exists a Carmichael number that is a strong pseudoprime to all prime bases less than 307^[2]. The BPSW algorithm uses a Lucas probable prime test on top of a Fermat prime test. There are few overlapping pseudoprimes between the Lucas and Fermat tests, making BPSW less likely to fail.

§ Legendre and Jacobi Symbols

Legendre Symbol

Given an integer $a$ and odd prime $p$ , the Legendre symbol is written as $\left(\frac{a}{p}\right)$ , and is defined by

\genfrac{(}{)}{}{}{a}{p} = \begin{cases} 0 & \text{ if } a \equiv_p 0\\ 1 & \text{ if } a \not\equiv_p 0 \text{ and } \exists x \in \mathbb{Z}_p: a \equiv_p x^2\\ -1 & \text{ if } a \not\equiv_p 0 \text{ and } \nexists x \in \mathbb{Z}_p: a \equiv_p x^2 \end{cases}

Jacobi Symbol

Given an integer $a$ and odd positive integer $n$ , the Jacobi symbol is written as $\left(\frac{a}{n}\right)$ , it is defined by the product of Legendre symbols,

\newcommand{\l}[2]{\genfrac{(}{)}{}{}{#1}{#2}} \l{a}{n} = \prod_{i=1}^{k} \l{a}{q_i}^{e_i}= \l{a}{q_1}^{e_1}\l{a}{q_2}^{e_2} \dots \l{a}{q_k}^{e_k}.

where $n = \prod_{i=1}^{k} q_i^{e_i} = q_1^{e_1}q_2^{e_2} \dots q_k^{e_k}$ .

Properties of the Jacobi:

Let $\genfrac{(}{)}{}{}{a}{1} = 1$ .
If $n$ is an odd prime, then the Jacobi is equivalent to the Legendre.
If $a \equiv_n b$ , then $\genfrac{(}{)}{}{}{a}{n} = \genfrac{(}{)}{}{}{b}{n} = \genfrac{(}{)}{}{}{a \pm m\cdot n}{n}$ .
$\genfrac{(}{)}{}{}{ab}{n} = \genfrac{(}{)}{}{}{a}{n}\genfrac{(}{)}{}{}{b}{n}$ $(\frac{ab}{n}) = (\frac{a}{n}) (\frac{b}{n})$ .
- $\genfrac{(}{)}{}{}{a^2}{n} = \genfrac{(}{)}{}{}{a}{n}^2$ .
$\genfrac{(}{)}{}{}{a}{mn} = \genfrac{(}{)}{}{}{a}{m}\genfrac{(}{)}{}{}{b}{n}$ $(\frac{a}{mn}) = (\frac{a}{m}) (\frac{b}{n})$ .
- $\genfrac{(}{)}{}{}{a}{n^2} = \genfrac{(}{)}{}{}{a}{n}^2$ .
$\genfrac{(}{)}{}{}{m}{n}\genfrac{(}{)}{}{}{n}{m} = (-1)^{\frac{m-1}{2}\cdot\frac{n-1}{2}}$ $(\frac{m}{n}) (\frac{n}{m}) = (- 1)^{\frac{m - 1}{2} \cdot \frac{n - 1}{2}}$ .
- $\genfrac{(}{)}{}{}{n}{1} = \genfrac{(}{)}{}{}{1}{n} = 1$ .
$\genfrac{(}{)}{}{}{-1}{n} = (-1)^{\frac{n-1}{2}}$ .
$\genfrac{(}{)}{}{}{2}{n} = (-1)^{\frac{n^2-1}{8}}$ .

Properties common between the Jacobi and Legendre:

If $\genfrac{(}{)}{}{}{a}{n} = -1$ then $a$ is a quadratic non-residue modulo $n$ .
If $a$ is a quadratic residue modulo $n$ , and $(a, n) = 1$ , then $\genfrac{(}{)}{}{}{a}{n} = 1$ .

As we will find out later, factorization is problem that lies in $\textbf{NP}\cap\textbf{coNP}$ as such we conjecture that there is no efficient (classical polynomial-time) algorithm to compute a non-trivial number's factorization. As such, relying on the formal definition of the Jacobi is impractical to do when testing very large integers for primality. Utilizing the properties of the Jacobi, we can compute the Jacobi in $\mathcal{O}(\log a \log n)$ time, as opposed to at best sub-exponential time using factorization.

§ The (Strong) Baillie-PSW Primality Test

Baillie-PSW

Suppose we want to determine if an odd positive integer $n$ is prime.

Perform a base 2 strong probable prime test.
- If $n$ is not a strong probable prime base 2, stop; $n$ is composite.
- This is effectively a Miller-Rabin test with base 2.
Find the first $D$ in the sequence $5, -7, 9, -11, 13, -15, \dots$ for which the Jacobi symbol $(D/n)$ is $-1$ . Set $P = 1, Q= (1-D) / 4$ .
Perform a strong Lucas probable prime test on $n$ using parameters $D, P, Q$ . If $n$ is not a strong Lucas probable prime, stop; $n$ is composite.
If the algorithm has not terminated, then $n$ is a probable prime.

Number Theoretic Functions, GNU MP Library Manual. ↩︎
Arnault, François. “Constructing Carmichael Numbers Which Are Strong Pseudoprimes to Several Bases.” Journal of Symbolic Computation, vol. 20, no. 2, 1995, pp. 151–161., https://doi.org/10.1006/jsco.1995.1042. ↩︎