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]).