Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Keyword
Articles 1 - 2 of 2
Full-Text Articles in Physical Sciences and Mathematics
Tabulating Pseudoprimes And Tabulating Liars, Andrew Shallue
Tabulating Pseudoprimes And Tabulating Liars, Andrew Shallue
Andrew Shallue
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 …
Constructing Carmichael Numbers Through Improved Subset-Product Algorithms, W.R. Alford, Jon Grantham, Steven Hayman, Andrew Shallue
Constructing Carmichael Numbers Through Improved Subset-Product Algorithms, W.R. Alford, Jon Grantham, Steven Hayman, Andrew Shallue
Andrew Shallue
We have constructed a Carmichael number with 10,333,229,505 prime factors, and have also constructed Carmichael numbers with 
prime factors for every 
between 3 and 19,565,220. These computations are the product of implementations of two new algorithms for the subset product problem that exploit the non-uniform distribution of primes 
with the property that 
divides a highly composite 
.
prime factors for every between 3 and 19,565,220. These computations are the product of implementations of two new algorithms for the subset product problem that exploit the non-uniform distribution of primes with the property that divides a highly composite .