5
$\begingroup$

Let $n=p_1^{a_1}\cdots p_k^{a_k}$ be an odd composite. Then the number of bases $1\le b\le n-1$ for which n is a strong pseudoprime is

$ \left(1 + \frac{2^{k\nu}-1}{2^k-1}\right) \prod_{i=1}^k\gcd\left(n^*,\ p_i^*\right) $

where $v_2(x)$ is the largest e such that $2^e|x-1$ and $\nu$ is the minimum of $v_2(p_i)$ over all the $p_i$, and $x^*$ is the largest odd divisor of $x-1$.

1. What is the analogous formula for pseudoprimes? I've seen it but misplaced the reference.

2. What is the original source of this formula? I've never seen an attribution, it's always stated as folk knowledge. Does it date back to the time of Fermat?

3. Similarly, what is the source of the formula above for strong pseudoprimes?

  • 0
    Well, I know something like this had to have been in one o$f$ Baillie's papers, but I've no idea if this showed up in other, earlier papers.2011-09-14

2 Answers 2

1

To answer (2), J.M. is correct that the formula for pseudoprimes appears in Baillie and Wagstaff. It was also published by Monier that same year.

To answer (3), Monier published that formula for the strong pseudoprimes. He also published one for Euler-Jacobi pseudoprimes.

I've checked a number of sources, and they all reference Monier and Baillie/Wagstaff. For example, Niven has the pseudoprime formula as an exercise, as does Pomerance and Crandall. Erdős and Pomerance give a nice presentation of all three formulas.

It seems those formulas never appeared in print before 1980. (They may have been generally known, but were unpublished.) If I had to guess, no one was interested in such formulas before then. Solovay and Strassen along with Miller and Rabin were the first to notice that those ideas could be made into practical probabilistic tests for primality, and they all published in the late 1970s.

2

Baillie and Wagstaff give a formula for counting the number of bases a number is pseudoprime to. Given a prime factorization $n=\prod\limits_{k}p_k^{a_k}$, the number of bases $< n$ for which $n$ is a pseudoprime is given by

$\prod_k \gcd(n-1,p_k-1)$

I have no idea if this has previously appeared before the Baillie-Wagstaff paper, though.