Open Access. Powered by Scholars. Published by Universities.®

Number Theory Commons™

Open Access. Powered by Scholars. Published by Universities.®

Miller-Rabin

Articles 1 - 2 of 2

Full-Text Articles in Number Theory

Tabulating Pseudoprimes And Tabulating Liars, Andrew Shallue Jan 2016

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 …

Go to article

Tabulating Pseudoprimes And Tabulating Liars, Andrew Shallue Dec 2015

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 …

Go to article