Quadratic residue

The square residual is a term from the mathematical branch number theory. A number is a quadratic residue with respect to a module if it is relatively prime to and there is a number, for which the congruence

Applies. For the special case of the latter is equivalent to saying that the rest of the division of a square number is by:

Exists for a prime number no solution to the above congruence, then it is called quadratic non-residue modulo. For non -prime numbers are not classified.

Example

In this example, the quadratic residues and non-residues of the module 6 can be determined. Since the numbers 0, 2, 3 and 4 are not relatively prime to 6, they are not classified. The classification of the figures 1 and 5, the following table of the squares of the numbers 0 to 5 is useful.

The number 1 is found in the right column and is therefore a square Rest The number 5, however, is a quadratic non-residue, because it is missing in the right column.

Simplified calculation of square numbers

For smaller numbers, the quadratic residues can be calculated relatively quickly: It is enough to look at the numbers, because and have the same remainder as well and, so also, and.

The calculation is demonstrated here by the example of the number 11.

0 mod 11 = 0; 1 mod 11 = 1; 4 mod 11 = 4; 9 mod 11 = 9 16 mod 11 = 5; 25 mod 11 = 3; 36 mod 11 = 3; 49 mod 11 = 5 64 mod 11 = 9; 81 mod 11 = 4; 100 mod 11 = 1 and 121 mod 11 = 0 You could go now, but the 0,1,4,9,5,3,3,5,9,4,1 cycle repeats itself again and again. Because of the symmetry relation only to calculate the square numbers less than 36 is required.

To calculate the square numbers, the relationship

Be used. The next square number can thus be calculated by adding all without multiplication. Thus, the quadratic residues are to be calculated for 11 very quickly in the head.

Multiplicative properties

Are quadratic residues modulo and then also a square rest is This can be shown simply by multiplying both numbers:

Jacobi symbol

For calculations in which one wants to prove whether a number is a quadratic residue, there are two shorthand available. The Legendre symbol indicates whether a number is a quadratic residue of a prime module:

This is generalized to the Jacobi symbol, which returns the calculation for arbitrary modules at their prime factorization:

As the Legendre symbol is the same for the prime modulus Jacobi symbol is to use the same shorthand not disadvantageous. As an important tool to calculate the Legendre symbol is the law of quadratic reciprocity with the first and second supplementary set available.

Application in cryptology

Especially in cryptology arises in many instances the task for a given number and a known modulus to decide if this number is a quadratic residue. This question is called Quadratic -residue problem. If the modulus is a prime number, this can be decided fairly simple. Otherwise, it raises some very difficult dar. particular, stating the quadratic -residue assumption that it is not practically possible for certain moduli to decide this question.

Quadratic residues with prime moduli

If the module is an odd prime, then the Euler's criterion provides an important statement about quadratic residues. A relatively prime to foreign is therefore a quadratic residue if and only if the following congruence holds:

From this it can be deduced that it is exactly quadratic residues and non-residues are as many square in a prime module.

The case of prime numbers and the Legendre symbol

The following is a prime number. And are not divisible, as is in the following table as a function of and, if the product is a quadratic residue (R) or non- residual (NR) is:

Another formulation of this statement is the following: the Legendre symbol satisfies the relation

For primes

From this relationship, the following statement can also be read off directly: is a quadratic residue modulo primes of the form and non- residue modulo primes of the form.

The peculiarity of 4

At the base of the 4 there for the odd square numbers only a quadratic residue, namely 1 (for or results in both cases, even numbers result ). The other odd number 3 thus is the quadratic non-residue, which means that no count after being squared, the rest of 3 modulo 4 can. In particular, the odd primes (ie p> 2) can now be divided into two groups:

• In such primes p, for which it holds, and it follows that square numbers n2 exist, for which:. For the primes of this group applies:

• In such primes p, for which it holds, and it follows that no square numbers n2 exist, for which:. For the primes of this group applies:

All even square numbers have the 4 as a factor, which can be simply show: . It follows that just applies to any square number.

Swell

• Peter Bundschuh: Introduction to Number Theory. 5th edition. Springer, 2002, ISBN 3-540-43579-4, pp. 124 and 127-147

• Number Theory