Searching for Patterns among Squares Modulo p

Abstract

Although squaring integers is deterministic, squares modulo a prime, $p$, appear to be random. First, because they are all generated by the multiplicative linear congruential equation, $x_{i+1}=g^2{x}_i\mathrm{mod}p$, where $x_0=1$ and $g$ is any primitive root of $p$, a pseudorandom number heuristic suggests that they are, in fact, unpredictable. Moreover, one type of cryptography makes use of discrete algorithms, which depends on the difficulty of solving $a=g^n$ for $n$ given $a$ and $g$. This suggests that the squares, which are exactly the even powers of $g$, are hard to identify. On the other hand, the Legendre symbol, $(a/p)$, which equals $1$ if a is a square modulo $p$ and $-1$ otherwise, has proven patterns. For example, $(ab/p)=(a/p)(b/p)$ holds true, and this shows that squares modulo $p$ have some structure. This paper considers the randomness of the following sequence: $(1/p),(2/p),...,((p-1)/p)$. Because it consists of binary data, the runs test is applied, which suggests that the number of runs is exactly (p-1)/2. This turns out to be a theorem proved by Aladov in 1896 that is not widely known. Consequently, this is an example of a number theory fact that is revealed naturally in a statistical setting, but one that has rarely been noted by mathematicians.

Joint Statistical Meetings 2016 Proceedings