Plots of quadratic residues (QRs in what follows) show some order besides
a general appearance of chaos. Applet 1 allows to display in a window QRs plots and to experiment with them.
You can change the modulus or increment or decrement it. Some acute parabolas are drawn in a
quite regular arrangement. Besides, the points that accumulate in the vertices of the
acute parabolas draw straight lines when 5040 divides the modulus or broader parabolas
in other cases. Those graphical patterns and the role of the "magic number" 5040 are analyzed
in Graphical patterns in quadratic residues.
The aim of this page is to analyze mathematically
the ordered features of QRs plots in an informal way. The quadratic residue
of an integer x modulo m is the remainder of the division
of x2 by m, then x2 = km + r,
where k is an appropriate integer that allows to represent the residues
r in the interval from 0 to m - 1. The graphical aspects
of QRs plots are closely related with rational numbers, then we consider
integers x close to the rational a/b m. Here, a/b
is an irreducible fraction. You can plot QRs one by one opening applet 2 and experiment with them. Note that the axes of the
graphic are X = x/m = a/b
and Y = r/m. At any moment, it is possible to change the
parameters (do not forget to press ENTER when a parameter is changed!), or
clear the plot.
The applet start plotting the QR of x0 ,
the closest integer to the rational 1/5 m. A big point appear
at X = 1/5 and at an ordinate Y whose value we do not
mind by the moment; we are better interested in the relative position of
the QRs of integers near x0 , say of x0
+ i, where i is a low positive or negative number. Pressing
the button in the applet, the residue of x0
+ 1 is plotted at a place labeled by P1. Repeating
the process, we plot the residues of x0 + 2, x0
+ 3, x0 + 4 ... and we note that the
QR of x0 + 5 is very close to P0
. Let us consider the difference (x0 + i)2 - x02
= 2x0i + i2. It is clear that
the difference between the QRs of x0 + i and
x0 is Δ = 2x0i + i2 - k m,
for some integer k. In order to estimate Δ, we do two approximations.
First, we substitute the rational a/b m for its nearest integer
x0, and second, we despise the i2
term. Then, the integer Δ is close to the rational 2a/b mi - km.
Let be a' ≡ 2ai (mod b), that is 2ai = a' + lb,
for some integer l. Then,
Δ ≈ 2a/b mi - km = (a' + lb)/b m - km = a'/b m -(k-l)m.
Since any choice can be done for the representation of the residue systems,
we set 0 ≤ a' < b and k = l,
then
Δ ≈ a'/b m with a' ≡ 2ai (mod
b). (*)
If we think the plot of QRs in the applet window as a cylinder where the
upper end of the graphic (for X = 1) is joined with the
bottom (for X =0), we can check that the separation of the places
Pi and Pi+1 is
2/5 m as holds applying the equation (*).
But, do not forget that we have done an approximation to guess the relative
position of the QRs. We press the button repeatedly
until reach the value i=35 about. Since the main approximation
we have done is to despise the term i2, we are plotting
something that seemingly is the right branches of five parabolas. Should
be the expected for i negative? ... We introduce i=0
in its text field and press repeatedly the bottom
and check the result.
The reader can repeat the operation for a=2 and b=5.
Now a'=2ai mod 5 = -i mod 5
(note that, in this case, for convenience we
have chosen a "lest absolute value system" to represent the residue classes).
But, what happens when b is even? ... The fraction 2a/b m
in the approximation of Δ turn to be a/b' m with
b' = b/2. Following identical reasoning as that done for b
odd, we arrive to the equivalence relation a' ≡ ai (mod
b'). We can note that all values for a' from 0 to b'-1
are possible because a and b are coprime. Then,
only b/2 parabolas are drawn in the plot when we experiment
with the parameters a=1, b=6 or a=3, b=8.
Do not forget that the above reasonings lie on approximations and we want
to know if the QRs near a fraction of the modulus spread as integer points
of real parabolas. For this purpose, we proceed using only integers and
avoiding any approximation. The nearest integer to x0
is exactly x0 = (am - α)/b where α ≡ am (mod
b) and |α| ≤ b/2. Besides α, we must to
define another "ad hoc" integer, β ≡ a2m - 2aα (mod
b2), that allows us to arrive, after doing some algebra,
to the following conclusions:
(i) The QRs for x near a fraction a/b of
the modulus spreads as integer points of a set of b (or b/2
if b is even) parabolas.
(ii) The parabolas are translations of the parabola y = x2.
All parabolas have their vertices at X = a/b. The vertex
of the parabola that contains x0 is at Y = β/b2.
They are all equally spaced in between.
Can we exploit this pretty order to seek for low QRs? ...For a given pair a
and b , we have a set of parabolas Pi where i runs
from 0 to b'-1 (here b'=b for b odd and b'=b/2 for
b even). For each value i, the integer points of Pi at x = x0 + i + b'j, j integer, are precisely the QRs of x. We can select the most upwards parabola
and calculate its index i. Once calculated its vertex coordinates,
we can calculate the optimal j value corresponding to
the lowest QR in absolute value. For this purpose, we need only the following
formulae;
α ≡ am (mod b) ,
|α| ≤ b/2,
β ≡ a2m - 2aα (mod
b2),
a' ≡ 2ai (mod b). for
b odd and a' ≡ ai (mod
b/2). for b even.
Note that the vertex of P0 is at β m/b2
and the vertex of Pi is a' times upwards
the regular separation between parabolas. This method yields QRs of O((bm)1/2) with
b < m1/3, then QRs grow from O(m1/2)
to O(m2/3) as b grows.
Something better can be done if we fix b and select the optimal value
of a. The reader can check that when β ≡ -1 (mod b),
the upper parabola have its vertex at -m/b2. Reducing
the above expression of β from modulo b2
to modulo b, it can be deduced that a ≡ m-1/2 (mod b).
In this case QRs are of O(m1/2) and b
must be under m1/4.
An example: Let m=7013 be as in the default example of the applet.
Note that m is quadratic residue modulo 17, then we set b=17
and found that for a=6, ma2 mod b = 1
(note that it is equivalent to say a ≡ m-1/2 (mod b)).
We calculate β that turns to be 135. Then we know that P0
is at 135 m/b2. From P0 upwards there
are polynomials at intervals of m/b. At the top is the polynomial
that we seek, the a'-th polynomial. Check that the desired value for
a' is a'=-(β+1)/b mod b=9. But we need to know the index of
such polynomial. We guess that it is i=5 because a' ≡ 2ai (mod
b) holds. With the help of the applet we check that we are right, the most
wanted polynomial is P5. Now we calculate x0=round(a/b
m) and we know that the integers points for x=x0+5+jb, j integer,
in P5 are QRs. We determine j values such that
x2 ≈ m/b2
(recall that each parabola is a translation of y=x2).
The generalized method.
Let f(x) be a function whose integer points we hope that splits
as integer points of some polynomials near some rational values of x.
The trick is to use the most fitted to our purposes polynomials instead of f(x)
(usually to seek for low values of f(x) ).
If f(x)= x2 mod m, the method allows us to find low QRs.
If f(x)= xn mod m, we can find low power residues or apply
the method to RSA cryptanalysis (Do not worry! this and lattice reduction attacks on RSA are avoided
with OAEP) on the basis of previous knowledge of the
hight bits of clear text (see this paper).
If f(x)= x3-round(x3/2)2, low values
of f(x) are good examples of Hall's conjecture. In this case
the splitting of the integer points of f(x) into polynomials occurs
near x=t2, t rational (see this preprint).