GRAPHICAL PATTERNS IN QUADRATIC RESIDUES.

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


 
Homepage of Ismael Jiménez Calvo