Square remainder

Quadratic remainder is a term from the mathematical branch of number theory . An integer is called a quadratic remainder with respect to a module if it is too prime and there is a number for which the congruence exists ${\displaystyle a}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle x}$

${\displaystyle a\equiv x^{2}{\pmod {m}}}$

holds, that is, and are in the same remainder class modulo . If there is no solution of the above congruence for a number that is too prime , then one calls the quadratic non-remainder modulo . To non-prime numbers are not classified, ie neither quadratic residues still quadratic non-residues. ${\displaystyle a}$ ${\displaystyle x^{2}}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle a}$ ${\displaystyle x}$ ${\displaystyle a}$ ${\displaystyle m}$ ${\displaystyle m}$

example

In this example, the square remainders and non-remainders of module 6 are determined. Since the numbers 0, 2, 3 and 4 are not relatively prime to 6, they are not classified. To classify the numbers 1 and 5, the following table of the squares of all numbers from 0 to 5 is helpful.

${\displaystyle x}$	${\displaystyle x^{2}}$	${\displaystyle x^{2}{\bmod {6}}}$
0	00	0
1	01	1
2	04th	4th
3	09	3
4th	16	4th
5	25th	1

The number 1 is in the right column and is therefore a quadratic remainder. The number 5, on the other hand, is a quadratic non-remainder, as it is missing in the right column.

Simplified calculation of the quadratic remainders

For smaller numbers , the quadratic remainders can be calculated relatively quickly: It is sufficient to consider the numbers , because and have the same remainder, as well as and , thus also and . ${\displaystyle m}$ ${\displaystyle 0\leq x\leq m/2}$ ${\displaystyle x^{2}}$ ${\displaystyle (x+k\cdot m)^{2}}$ ${\displaystyle x^{2}}$ ${\displaystyle (-x)^{2}}$ ${\displaystyle x^{2}}$ ${\displaystyle (m-x)^{2}}$

The calculation is demonstrated here using the module as an example . ${\displaystyle m=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; 121 mod 11 = 0

If you continue like this, the cycle (0, 1, 4, 9, 5, 3, 3, 5, 9, 4, 1) repeats itself over and over again. Because of the symmetry relationship, one can restrict oneself to the reduction of the square numbers that are not greater than . ${\displaystyle (m-x)^{2}\equiv x^{2}{\pmod {m}}}$ ${\displaystyle \lfloor m/2\rfloor ^{2}=25}$

To calculate the square numbers, the relationship

${\displaystyle \left({n+1}\right)^{2}=n^{2}+2\cdot n+1}$

be used. So the next square number can be calculated by adding without any multiplication. This allows you to quickly calculate the quadratic remainder for module in your head. ${\displaystyle 2n+1}$ ${\displaystyle m=11}$

This results in a (symmetrical) pattern with the following cycles:

mod  2: (0, 1) 
mod  3: (0, 1, 1)
mod  4: (0, 1)
mod  5: (0, 1, 4, 4, 1)
mod  6: (0, 1, 4, 3, 4, 1)
mod  7: (0, 1, 4, 2, 2, 4, 1)
mod  8: (0, 1, 4, 1,)
mod  9: (0, 1, 4, 0, 7, 7, 0, 4, 1)
mod 10: (0, 1, 4, 9, 6, 5, 6, 9, 4, 1)
mod 11: (0, 1, 4, 9, 5, 3, 3, 5, 9, 4, 1)
mod 12: (0, 1, 4, 9, 4, 1)
mod 13: (0, 1, 4, 9, 3, 12, 10, 10, 12, 3, 9, 4, 1)
mod 14: (0, 1, 4, 9, 2, 11, 8, 7, 8, 11, 2, 9, 4, 1)
mod 15: (0, 1, 4, 9, 1, 10, 6, 4, 4, 6, 10, 1, 9, 4, 1)
mod 16: (0, 1, 4, 9)
mod 17: (0, 1, 4, 9, 16, 8, 2, 15, 13, 13, 15, 2, 8, 16, 9, 4, 1)
mod 18: (0, 1, 4, 9, 16, 7, 0, 13, 10, 9, 10, 13, 0, 7, 16, 9, 4, 1)
mod 19: (0, 1, 4, 9, 16, 6, 17, 11, 7, 5, 5, 7, 11, 17, 6, 16, 9, 4, 1)
mod 20: (0, 1, 4, 9, 16, 5, 16, 9, 4, 1)
 …

The cycles of the modules divisible by 4 occur several times in the pattern.

Multiplicative properties

If and are square remainder modulo , then is also square remainder. This can be shown simply by multiplying both numbers: Off ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle m}$ ${\displaystyle ab}$

${\displaystyle a\equiv x^{2}{\pmod {m}}}$

${\displaystyle b\equiv y^{2}{\pmod {m}}}$

follows first

${\displaystyle a=x^{2}+t\cdot m}$

${\displaystyle b=y^{2}+u\cdot m}$

with two whole numbers and . Now a multiplication yields ${\displaystyle t}$ ${\displaystyle u}$

${\displaystyle a\cdot b=(xy)^{2}+v\cdot m}$

with the whole number from which ${\displaystyle v=ux^{2}+ty^{2}+tum}$

${\displaystyle ab\equiv (xy)^{2}{\pmod {m}}}$

follows such that with and the product is also a quadratic remainder. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle ab}$

Legendre and Jacobi symbol

Two abbreviations are available for calculations in which you want to prove whether a number is a quadratic remainder. The Legendre symbol indicates whether a number is a quadratic remainder for a prime module:

${\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}\quad 1,&{\mbox{wenn }}a{\mbox{ quadratischer Rest modulo }}p{\mbox{ ist}}\\-1,&{\mbox{wenn }}a{\mbox{ quadratischer Nichtrest modulo }}p{\mbox{ ist}}\\\quad 0,&{\mbox{wenn }}a{\mbox{ ein Vielfaches von }}p{\mbox{ ist}}\end{cases}}}$

This is generalized to the Jacobi symbol , which reduces the calculation for any modules to their prime factorization : ${\displaystyle m=p_{1}^{\nu _{1}}\cdot p_{2}^{\nu _{2}}\cdot \ldots \cdot p_{k}^{\nu _{k}}}$

${\displaystyle \left({\frac {a}{m}}\right)=\left({\frac {a}{p_{1}}}\right)^{\nu _{1}}\cdot \left({\frac {a}{p_{2}}}\right)^{\nu _{2}}\cdot \ldots \cdot \left({\frac {a}{p_{k}}}\right)^{\nu _{k}}}$

Since the Jacobi symbol provides the same values ​​for prime number modules as the Legendre symbol, the use of the same shorthand is not a disadvantage. The quadratic reciprocity law with the first and second supplementary theorem is an important tool for calculating the Legendre symbol . It should be noted, however, that the Jacobi symbol does not clearly indicate whether a number is a square remainder, for example , but 2 is not a square remainder modulo 15. ${\displaystyle \left({\frac {2}{15}}\right)=1}$

Application in cryptology

In cryptology in particular , there is often the task of deciding for a given number and a known module whether this number is a square remainder for the module. This question is called the quadratic remainder problem . If the module is a prime number , this can be decided quite easily. Otherwise it turns out to be quite difficult in some cases . In particular, the square remainder assumption says that it is practically impossible to answer this question for certain modules.

Quadratic remainders in prime modules

If the module is an odd prime number , Euler's criterion provides an important statement about quadratic residues. A too coprime remainder is therefore a quadratic remainder if and only if the following congruence holds: ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle a}$

${\displaystyle a^{\frac {p-1}{2}}\equiv 1{\pmod {p}}}$

From this it can be deduced that for an odd prime module there are exactly square residues and just as many square non-residues. ${\displaystyle p}$ ${\displaystyle {\tfrac {p-1}{2}}}$

The case of prime numbers and the Legendre symbol

In the following it is a prime number. If neither nor is divisible by, the following table indicates whether the product is a quadratic remainder (R) or a non-remainder (NR), depending on and : ${\displaystyle m=p}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle p}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle ab}$

	a R	a NO
b R	from R	from NO
b NO	from NO	from R

This can also be formulated as follows: The following always applies to the Legendre symbol

${\displaystyle \left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right).}$

For odd prime numbers the following applies

${\displaystyle \left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}{\pmod {p}}.}$

The following statement can also be read directly from this relationship:

${\displaystyle -1}$is a quadratic remainder modulo prime numbers of form and non- remainder modulo prime numbers of form . ${\displaystyle 4k+1}$ ${\displaystyle 4k+3}$

The specialty of the 4

Modulo 4 there is only one quadratic residue, namely 1. Because both as well as for results and for even numbers applies . 3 is therefore a quadratic non-remainder, which means that no square number modulo 4 leaves the remainder 3. The odd prime numbers (i.e. all but 2) can therefore be divided into two groups: ${\displaystyle n\equiv 1{\pmod {4}}}$ ${\displaystyle n\equiv 3{\pmod {4}}}$ ${\displaystyle n^{2}\equiv 1{\pmod {4}}}$ ${\displaystyle n}$ ${\displaystyle n^{2}\equiv 0{\pmod {4}}}$

• Prime numbers for which the following applies: For them there exist square numbers with . The following applies to the prime numbers of this group: ${\displaystyle p}$ ${\displaystyle p\equiv 1{\pmod {4}}}$ ${\displaystyle n^{2}}$ ${\displaystyle n^{2}\equiv (p-1){\pmod {p}}}$

${\displaystyle (p-1)^{\frac {p-1}{2}}\equiv 1{\pmod {p}}}$

You can do this with the Legendre symbol

${\displaystyle \left({\frac {p-1}{p}}\right)=1}$

write or shorter:

${\displaystyle \left({\frac {-1}{p}}\right)=1}$

• Prime numbers for which the following applies: There are no square numbers with . The following applies to the prime numbers of this group: ${\displaystyle q}$ ${\displaystyle q\equiv 3{\pmod {4}}}$ ${\displaystyle n^{2}}$ ${\displaystyle n^{2}\equiv (q-1){\pmod {q}}}$

${\displaystyle (q-1)^{\frac {q-1}{2}}\equiv (q-1){\pmod {q}}}$

${\displaystyle \left({\frac {q-1}{q}}\right)=-1}$

${\displaystyle \left({\frac {-1}{q}}\right)=-1}$

literature

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