I am fascinated by problems where deep "pure" mathematics
has tangible results;
computational
number theory
is a
prime
source of such problems. Thanks to modern
cryptography,
problems like
integer
factorization
have real-world consequences.

This page lists a few of my favorite questions
in computational number theory. (In this list my
interest in
quadratic forms
is readily apparent.)

### Prime-proving algorithms

Many cryptographic schemes need large primes. We
find them
essentially by picking random numbers until one is
prime. But how do we
check if a number is prime?
The
most commonly used test
is
probabilistic.
It works quite well in practice but is not fully satisfying
from a theoretical perspective.

Several
deterministic
algorithms
are known, including
one
which was
famously
[pdf]
an undergraduate research project (sometimes called the
"best
senior thesis project ever"). I am interested
in the math behind these algorithms, how they compare in
theory and in practice, and the extent to which they
can be improved.

Here [pdf]
is a report I wrote in college in which I implemented and compared
the three major deterministic algorithms.

### Computing explicit equivalences between quadratic forms

Given two
rational quadratic forms,
we know
how to
test
if they are equivalent. We even know a way
to make the test effective
[pdf].
However, using these methods to actually compute explicit rational
equivalences does not seem to have been previously done.

Given two
indefinite
integral quadratic forms
of rank at least 3, the
spinor genus
gives a way to test if the forms are equivalent. Given an
algorithm for computing rational equivalences (as above),
this test is in principle effective. It also does not seem
to have been done before.

I developed Sage
code for these problems. The rational equivalence code
is in an
alpha phase
and the integral equivalence code is pre-pre-alpha.

### Sums of three squares

It is well-known which positive integers are sums of
two squares and
four squares,
and in both cases efficient algorithms
are known
for finding an explicit representation. It is also well-known
which positive integers are sums of three squares,
but in that case the
algorithmic problem
is much less developed.

I discussed one approach for a better algorithm in my
effective proof
[pdf]
notes, but I think it could be improved further
(see Problem 12 in my
thesis proposal
[pdf]).