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 x^{2 } by m, then x^{2} = 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 x_{0 },
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 x_{0 }, say of x_{0}
+ i, where i is a low positive or negative number. Pressing
the button in the applet, the residue of x_{0}
+ 1 is plotted at a place labeled by P_{1}. Repeating
the process, we plot the residues of x_{0} + 2, x_{0}
+ 3, x_{0} + 4 ... and we note that the
QR of x_{0} + 5 is very close to P_{0}
. Let us consider the difference (x_{0} + i)^{2} - x_{0}^{2}
= 2x_{0}i + i^{2}. It is clear that
the difference between the QRs of x_{0} + i and
x_{0} is Δ = 2x_{0}i + i^{2} - 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
x_{0}, and second, we despise the i^{2}
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
P_{i} and P_{i+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 i^{2}, 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 x_{0}
is exactly x_{0} = (am - α)/b where α ≡ am (mod
b) and |α| ≤ b/2. Besides α, we must to
define another "ad hoc" integer, β ≡ a^{2}m - 2aα (mod
b^{2}), 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 = x^{2}.
All parabolas have their vertices at X = a/b. The vertex
of the parabola that contains x_{0} is at Y = β/b^{2}.
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 P_{i} 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 P_{i} at x = x_{0} + 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,

β ≡ a^{2}m - 2aα (mod
b^{2}),

a' ≡ 2ai (mod b). for
b odd and a' ≡ ai (mod
b/2). for b even.

Note that the vertex of P_{0} is at β m/b^{2}
and the vertex of P_{i} is a' times upwards
the regular separation between parabolas. This method yields QRs of O((bm)^{1/2}) with
b < m^{1/3}, then QRs grow from O(m^{1/2})
to O(m^{2/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/b^{2}. Reducing
the above expression of β from modulo b^{2}
to modulo b, it can be deduced that a ≡ m^{-1/2} (mod b).
In this case QRs are of O(m^{1/2}) and b
must be under m^{1/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, ma^{2} 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 P_{0}
is at 135 m/b^{2}. From P_{0} 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 P_{5}. Now we calculate x_{0}=round(a/b
m) and we know that the integers points for x=x_{0}+5+jb, j integer,
in P_{5} are QRs. We determine j values such that
x^{2} ≈ m/b^{2}
(recall that each parabola is a translation of y=x^{2}).

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)= x^{2} mod m, the method allows us to find low QRs.
If f(x)= x^{n} 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)= x^{3}-round(x^{3/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=t^{2}, t rational (see this preprint).