Open Access. Powered by Scholars. Published by Universities.®
- Discipline
- Keyword
Articles 1 - 6 of 6
Full-Text Articles in Number Theory
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 …
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
Scholarship
style="color: rgb(51, 51, 51); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;">We have constructed a Carmichael number with 10,333,229,505 prime factors, and have also constructed Carmichael numbers with style="color: rgb(51, 51, 51); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;"> prime factors for every style="color: rgb(51, 51, 51); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;"> 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 style="color: rgb(51, 51, 51); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;">with the property that …
Constructing Large Numbers With Cheap Computers, Andrew Shallue, Steven Hayman
Constructing Large Numbers With Cheap Computers, Andrew Shallue, Steven Hayman
Scholarship
No abstract provided.
An Improved Multi-Set Algorithm For The Dense Subset Sum Problem, Andrew Shallue
An Improved Multi-Set Algorithm For The Dense Subset Sum Problem, Andrew Shallue
Scholarship
No abstract provided.
Two Number-Theoretic Problems That Illustrate The Power And Limitations Of Randomness, Andrew Shallue
Two Number-Theoretic Problems That Illustrate The Power And Limitations Of Randomness, Andrew Shallue
Scholarship
This thesis contains work on two problems in algorithmic number theory. The first problem is to give an algorithm that constructs a rational point on an elliptic curve over a finite field. A fast and easy randomized algorithm has existed for some time. We prove that in the case where the finite field has characteristic 2, there is a deterministic algorithm with the same asymptotic running time as the existing randomized algorithm.
Construction Of Rational Points On Elliptic Curves Over Finite Fields, Andrew Shallue, Christiaan Van De Woestijne
Construction Of Rational Points On Elliptic Curves Over Finite Fields, Andrew Shallue, Christiaan Van De Woestijne
Scholarship
We give a deterministic polynomial-time algorithm that computes a nontrivial rational point on an elliptic curve over a finite field, given a Weierstrass equation for the curve. For this, we reduce the problem to the task of finding a rational point on a curve of genus zero.