Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Publication Type
Articles 1 - 2 of 2
Full-Text Articles in Physical Sciences and Mathematics
Parallel Infeasibility Analysis, Wenting Zhao, Mark Liffiton, Faculty Advisor
Parallel Infeasibility Analysis, Wenting Zhao, Mark Liffiton, Faculty Advisor
John Wesley Powell Student Research Conference
Oral presentation abstract.
Tabulating Pseudoprimes And Tabulating Liars, Andrew Shallue
Tabulating Pseudoprimes And Tabulating Liars, Andrew Shallue
Scholarship
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 …