![](https://d3ilqtpdwi981i.cloudfront.net/tuewwxyw1pc-eDKETcNQqCxwfqo=/425x550/smart/https://bepress-attached-resources.s3.amazonaws.com/uploads/01/ff/7a/01ff7a21-209c-495c-9ace-6e6a2f638d2d/thumbnail_BPFile%20object.jpg)
Other
Tabulating pseudoprimes and tabulating liars
(2016)
Abstract
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.
Keywords
- Miller-Rabin,
- strong pseudoprime,
- strong liar
Disciplines
Publication Date
2016
Citation Information
Andrew Shallue. "Tabulating pseudoprimes and tabulating liars" (2016) Available at: http://works.bepress.com/andrew_shallue/7/
Creative Commons license
![Creative Commons License](https://i.creativecommons.org/l/by-nc/4.0/88x31.png)
This work is licensed under a Creative Commons CC_BY-NC International License.