Quadratic residue

We try to estimate the function H(u), noted H, by minimization of the quadratic residual error... 

In some cases when estimates of the pure-error mean square are unavailable owing to lack of replicated data, more approximate methods of testing lack of fit may be used. Here, quadratic terms would be added to the models of Eqs. (32) and (33), the complete model would be fitted to the data, and a residual mean square calculated. Assuming this quadratic model will adequately fit the data (lack of fit unimportant), this quadratic residual mean square may be used in Eq. (68) in place of the pure-error mean square. The lack-of-fit mean square in this equation would be the difference between the linear residual mean square [i.e., using Eqs. (32) and (33)] and the quadratic residual mean square. A model should be rejected only if the ratio is very much greater than the F statistic, however, since these two mean squares are no longer independent. 

Most of the following facts are only needed in the constructions based on the factoring assumption. There, the basic structure used is the ring of integers modulo n, where n is a chosen number that is hopefully hard to factor. Particular attention is paid to quadratic residues and square roots, because the squaring function plays an important part in the following schemes. 

A quadratic residue modulo w is an element of that has a square root. The set of quadratic residues, denoted by QR, is a subgroup. Thus y e QR o 3vv w sy mod n. The remaining elements are called quadratic nonresidues (although they are residues and not quadratic). 

For an odd prime p, exactly half of the elements of Zp are quadratic residues, and each one has two square roots w. The quadratic residues are characterized by the Legendre symbol 0, which is defined as +1 if y is a quadratic residue and -1 otherwise (and 0 for y = 0 mod p). The Legendre symbol can be computed efficiently with Euler s criterion = y(P l) 2... 

Modulo a prime power, pL where p 2, a number y is a quadratic residue if and only if it is one modulo p. Furthermore, each quadratic residue has two square roots again. This can be seen by considering the isomorphism with the additive group modulo 0 = (p - l)p If g is a generator, exactly the elements with an even exponent e are the quadratic residues, and g and are the roots. 

The situation modulo a general odd n can be derived with the Chinese remainder theorem A number y is a quadratic residue modulo n if and only if it is one modulo each prime factor of n. If n has i distinct prime factors, the number of square roots of each quadratic residue is 2, and l(2 l = IZ I / 2. ... 

Secondly, the two roots Wp of a quadratic residue mod p have different Legendre symbols, and similarly for q. Hence the four roots of a quadratic residue mod n are mapped to all the four different values (1, 1), (1, -1), (-1, 1), and (-1, -1) by Xn-In particular, two of them have the Jacobi symbol +1 they form a pair w and exactly one of them is a quadratic residue. 

Squaring is not a permutation on any of QRfi, RQR% or RQR for arbitrary n, not even in 4N + 1. For instance, if n=pq with p, q prime and psq = mod 4, then 2Tn( l) = ( > D-Hence either all the four roots of a quadratic residue are quadratic residues again, or none is. Thus squaring is 4-to-l on QR . The four roots form two different classes in QRjJ[ thus squaring is not 1-to-l on RQR either. Even more obviously, squaring is not a permutation on RQR% in general, because its range is at most the subset RQR%... 

Given the complexity of the multiplication process, it is surprising that the multiplication group of a Galois field has the simple structure of a cyclic group. This means that we can find a primitive element g such that each nonzero mark can be represented by some power of g. Multiplication of nonzero marks in GF p ) is equivalent to addition of powers modulo p — l. If p is an odd prime, we can separate the nonzero marks into squares and not-squares. The squares can result from squaring and are even powers of g, the not-squares cannot result from squaring another mark, and are odd powers of g. The set of all squares is called the quadratic residue set. 

The secure Blum-Blum-Shub generator, developed by Lenore Blum, Manuel Blum, and Michael Shub in 1986, is based on the believed computational difficulty of distinguishing quadratic residues modulo n from certain kinds of nonquadratic residues modulo n. 

The first row of every category indicates the observed frequency (fo). The second row indicates the expected frequency (/,) and the quadratic residue Blue colored frequencies show significantly (p = 0.05) lower speed estimation. Red colored frequencies show a significantly (p = 0.05) higher estimation. Thus, it is shown that the perceived velocity is manipulated by the motion blur rendering and is therefore suited to convey the information of a fast approaching vehicle... 

---