|
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 (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 (mod 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.
|
