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

Number Theory Commons™

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

Selected Works

Articles 1 - 12 of 12

Full-Text Articles in Number Theory

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

The Combinatorialization Of Linear Recurrences, Arthur T. Benjamin, Halcyon Derks, Jennifer J. Quinn Feb 2014

The Combinatorialization Of Linear Recurrences, Arthur T. Benjamin, Halcyon Derks, Jennifer J. Quinn

Jennifer J. Quinn

We provide two combinatorial proofs that linear recurrences with constant coefficients have a closed form based on the roots of its characteristic equation. The proofs employ sign-reversing involutions on weighted tilings.

Go to article

Constructing Carmichael Numbers Through Improved Subset-Product Algorithms, W.R. Alford, Jon Grantham, Steven Hayman, Andrew Shallue Dec 2013

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 .

Go to article

Circular Units Of Function Fields, Frederick Harrop Apr 2012

Circular Units Of Function Fields, Frederick Harrop

Frederick F Harrop

A unit index-class number formula is proved for subfields of cyclotomic function fields in analogy with similar results for subfields of cyclotomic number fields.

Go to article

Computing Local Constants For Cm Elliptic Curves, Sunil Chetty, Lung Li Apr 2012

Computing Local Constants For Cm Elliptic Curves, Sunil Chetty, Lung Li

Sunil Chetty

Let E/k be an elliptic curve with CM by O. We determine a formula for (a generalization of) the arithmetic local constant of Mazur-Rubin at almost all primes of good reduction. We apply this formula to the CM curves defined over Q and are able to describe extensions F/Q over which the O-rank of E grows.

Go to article

Computing Local Constants Of Cm Elliptic Curves, Sunil Chetty, Lung Li Dec 2011

Computing Local Constants Of Cm Elliptic Curves, Sunil Chetty, Lung Li

Sunil Chetty

Let E/k be an elliptic curve with CM by O. We determine a formula for (a generalization of) the arithmetic local constant of Mazur-Rubin at almost all primes of good reduction. We apply this formula to the CM curves defined over Q and are able to describe extensions F/Q over which the O-rank of E grows.

Go to article

Constructing Large Numbers With Cheap Computers, Andrew Shallue, Steven Hayman Oct 2011

Constructing Large Numbers With Cheap Computers, Andrew Shallue, Steven Hayman

Andrew Shallue

No abstract provided.

Go to article

An Improved Multi-Set Algorithm For The Dense Subset Sum Problem, Andrew Shallue Apr 2008

An Improved Multi-Set Algorithm For The Dense Subset Sum Problem, Andrew Shallue

Andrew Shallue

No abstract provided.

Go to article

Two Number-Theoretic Problems That Illustrate The Power And Limitations Of Randomness, Andrew Shallue Dec 2006

Two Number-Theoretic Problems That Illustrate The Power And Limitations Of Randomness, Andrew Shallue

Andrew Shallue

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.

Go to article

Construction Of Rational Points On Elliptic Curves Over Finite Fields, Andrew Shallue, Christiaan E. Van De Woestijne Dec 2005

Construction Of Rational Points On Elliptic Curves Over Finite Fields, Andrew Shallue, Christiaan E. Van De Woestijne

Andrew Shallue

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.

Go to article

Visualizing Patterns In The Integers Relating To The Abundancy Index, Judy Holdener Dec 2004

Visualizing Patterns In The Integers Relating To The Abundancy Index, Judy Holdener

Judy Holdener

n/a

Go to article

Group Actions In Number Theory, Tyler J. Evans Jul 2004

Group Actions In Number Theory, Tyler J. Evans

Tyler Evans

Students having had a semester course in abstract algebra are
exposed to the elegant way in which one can use the theory of finite
cyclic groups to derive familiar results from Number Theory.
We present 3 examples suitable for a second semester course in
algebra.
Each uses the notion of the action of a group on a set.
This work was done with Ben Holt, who, at the time, was an HSU
undergraduate student taking second semester algebra

Go to article