Tabulating pseudoprimes and tabulating liars

Research output: Other contribution


This paper explores the asymptotic complexity of two problems related 
to the Miller-Rabin-Selfridge primality test.  The first problem is to 
tabulate strong pseudoprimes to a single fixed base $a$.  It is now proven 
that tabulating up to $x$ requires $O(x)$ arithmetic operations and $O(x\log{x})$ bits of space.
The second problem is to find all strong liars and witnesses, given a fixed odd composite $n$.
This appears to be unstudied, and a randomized algorithm is presented that requires an 
expected $O((\log{n})^2 + |S(n)|)$ operations (here $S(n)$ is the set of strong liars).
Although interesting in their own right, a notable application is the search for sets of 
composites with no reliable witness.

Original languageAmerican English
StatePublished - 2016


  • Miller-Rabin
  • strong pseudoprime
  • strong liar


  • Theory and Algorithms
  • Number Theory

Cite this