Movatterモバイル変換

[0]ホーム

Jump to content

Quadratic residue

Edit links

From Wikipedia, the free encyclopedia

Integer that is a perfect square modulo some integer

Innumber theory, anintegerq is aquadratic residuemodulon if it iscongruent to aperfect square modulon; that is, if there exists an integerx such that

x^{2}\equiv q{\pmod {n}}.

Otherwise,q is aquadratic nonresidue modulon.

Quadratic residues are used in applications ranging fromacoustical engineering tocryptography and thefactoring of large numbers.

History, conventions, and elementary facts

Fermat,Euler,Lagrange,Legendre, and other number theorists of the 17th and 18th centuries established theorems^[1] and formed conjectures^[2] about quadratic residues, but the first systematic treatment is § IV ofGauss'sDisquisitiones Arithmeticae (1801). Article 95 introduces the terminology "quadratic residue" and "quadratic nonresidue", and says that if the context makes it clear, the adjective "quadratic" may be dropped.

For a givenn, a list of the quadratic residues modulon may be obtained by simply squaring all the numbers 0, 1, ...,n − 1. Sincea≡b (modn) impliesa²≡b² (modn), any other quadratic residue is congruent (modn) to some in the obtained list. But the obtained list is not composed of mutually incongruent quadratic residues (mod n) only. Sincea²≡(n−a)² (modn), the list obtained by squaring all numbers in the list 1, 2, ...,n − 1 (or in the list 0, 1, ...,n) is symmetric (modn) around its midpoint, hence it is actually only needed to square all the numbers in the list 0, 1, ..., $\lfloor$ n/2 $\rfloor$ . The list so obtained may still contain mutually congruent numbers (modn). Thus, the number of mutually noncongruent quadratic residues modulon cannot exceedn/2 + 1 (n even) or (n + 1)/2 (n odd).^[3]

The product of two residues is always a residue.

Prime modulus

Modulo 2, every integer is a quadratic residue.

Modulo an oddprime numberp there are (p + 1)/2 residues (including 0) and (p − 1)/2 nonresidues, byEuler's criterion. In this case, it is customary to consider 0 as a special case and work within themultiplicative group of nonzero elements of thefield $(\mathbb {Z} /p\mathbb {Z} )$ . In other words, every congruence class except zero modulop has a multiplicative inverse. This is not true for composite moduli.^[4]

Following this convention, the multiplicative inverse of a residue is a residue, and the inverse of a nonresidue is a nonresidue.^[5]

Following this convention, modulo an odd prime number there is an equal number of residues and nonresidues.^[4]

Modulo a prime, the product of two nonresidues is a residue and the product of a nonresidue and a (nonzero) residue is a nonresidue.^[5]

The first supplement^[6] to thelaw of quadratic reciprocity is that ifp ≡ 1 (mod 4) then −1 is a quadratic residue modulop, and ifp ≡ 3 (mod 4) then −1 is a nonresidue modulop. This implies the following:

Ifp ≡ 1 (mod 4) the negative of a residue modulop is a residue and the negative of a nonresidue is a nonresidue.

Ifp ≡ 3 (mod 4) the negative of a residue modulop is a nonresidue and the negative of a nonresidue is a residue.

Prime power modulus

All odd squares are ≡ 1 (mod 8) and thus also ≡ 1 (mod 4). Ifa is an odd number andm = 8, 16, or some higher power of 2, thena is a residue modulom if and only ifa ≡ 1 (mod 8).^[7]

For example, mod (32) the odd squares are
1² ≡ 15² ≡ 1
3² ≡ 13² ≡ 9
5² ≡ 11² ≡ 25
7² ≡ 9² ≡ 49 ≡ 17
and the even ones are
0² ≡ 8² ≡ 16² ≡ 0
2² ≡ 6²≡ 10² ≡ 14²≡ 4
4² ≡ 12² ≡ 16.

So a nonzero number is a residue mod 8, 16, etc., if and only if it is of the form 4^k(8n + 1).

A numbera relatively prime to an odd primep is a residue modulo any power ofp if and only if it is a residue modulop.^[8]

If the modulus ispⁿ,

thenp^ka

is a residue modulopⁿ ifk ≥n

is a nonresidue modulopⁿ ifk <n is odd

is a residue modulopⁿ ifk <n is even anda is a residue

is a nonresidue modulopⁿ ifk <n is even anda is a nonresidue.^[9]

Notice that the rules are different for powers of two and powers of odd primes.

Modulo an odd prime powern =p^k, the products of residues and nonresidues relatively prime top obey the same rules as they do modp;p is a nonresidue, and in general all the residues and nonresidues obey the same rules, except that the products will be zero if the power ofp in the product ≥n.

Modulo 8, the product of the nonresidues 3 and 5 is the nonresidue 7, and likewise for permutations of 3, 5 and 7. In fact, the multiplicative group of the non-residues and 1 form theKlein four-group.

Composite modulus not a prime power

The basic fact in this case is

ifa is a residue modulon, thena is a residue modulop^k forevery prime power dividingn.

ifa is a nonresidue modulon, thena is a nonresidue modulop^k forat least one prime power dividingn.

Modulo a composite number, the product of two residues is a residue. The product of a residue and a nonresidue may be a residue, a nonresidue, or zero.

For example, from the table for modulus 6 1, 2,3,4, 5 (residues inbold).
The product of the residue 3 and the nonresidue 5 is the residue 3, whereas the product of the residue 4 and the nonresidue 2 is the nonresidue 2.

Also, the product of two nonresidues may be either a residue, a nonresidue, or zero.

For example, from the table for modulus 15 1, 2, 3,4, 5,6, 7, 8,9,10, 11, 12, 13, 14 (residues inbold).
The product of the nonresidues 2 and 8 is the residue 1, whereas the product of the nonresidues 2 and 7 is the nonresidue 14.

This phenomenon can best be described using the vocabulary of abstract algebra. The congruence classes relatively prime to the modulus are agroup under multiplication, called thegroup of units of thering $(\mathbb {Z} /n\mathbb {Z} )$ , and the squares are asubgroup of it. Different nonresidues may belong to differentcosets, and there is no simple rule that predicts which one their product will be in. Modulo a prime, there is only the subgroup of squares and a single coset.

The fact that, e.g., modulo 15 the product of the nonresidues 3 and 5, or of the nonresidue 5 and the residue 9, or the two residues 9 and 10 are all zero comes from working in the full ring $(\mathbb {Z} /n\mathbb {Z} )$ , which haszero divisors for compositen.

For this reason some authors^[10] add to the definition that a quadratic residuea must not only be a square but must also berelatively prime to the modulusn. (a is coprime ton if and only ifa² is coprime ton.)

Although it makes things tidier, this article does not insist that residues must be coprime to the modulus.

Notations

Gauss^[11] usedR andN to denote residuosity and non-residuosity, respectively;

for example,2 R 7 and5 N 7, or1 R 8 and3 N 8.

Although this notation is compact and convenient for some purposes,^[12]^[13] a more useful notation is theLegendre symbol, also called thequadratic character, which is defined for all integersa and positive oddprime numbersp as

\left({\frac {a}{p}}\right)={\begin{cases}\;\;\,0&{\text{ if }}p{\text{ divides }}a\\+1&{\text{ if }}a\operatorname {R} p{\text{ and }}p{\text{ does not divide }}a\\-1&{\text{ if }}a\operatorname {N} p{\text{ and }}p{\text{ does not divide }}a\end{cases}}

There are two reasons why numbers ≡ 0 (modp) are treated specially. As we have seen, it makes many formulas and theorems easier to state. The other (related) reason is that the quadratic character is ahomomorphism from themultiplicative group of nonzero congruence classes modulop to thecomplex numbers under multiplication. Setting $({\tfrac {np}{p}})=0$ allows itsdomain to be extended to the multiplicativesemigroup of all the integers.^[14]

One advantage of this notation over Gauss's is that the Legendre symbol is a function that can be used in formulas.^[15] It can also easily be generalized tocubic, quartic and higher power residues.^[16]

There is a generalization of the Legendre symbol for composite values ofp, theJacobi symbol, but its properties are not as simple: ifm is composite and the Jacobi symbol $({\tfrac {a}{m}})=-1,$ thena Nm, and ifa Rm then $({\tfrac {a}{m}})=1,$ but if $({\tfrac {a}{m}})=1$ we do not know whethera Rm ora Nm. For example: $({\tfrac {2}{15}})=1$ and $({\tfrac {4}{15}})=1$ , but2 N 15 and4 R 15. Ifm is prime, the Jacobi and Legendre symbols agree.

Distribution of quadratic residues

Although quadratic residues appear to occur in a rather random pattern modulon, and this has been exploited in suchapplications asacoustics andcryptography, their distribution also exhibits some striking regularities.

UsingDirichlet's theorem on primes inarithmetic progressions, thelaw of quadratic reciprocity, and theChinese remainder theorem (CRT) it is easy to see that for anyM > 0 there are primesp such that the numbers 1, 2, ...,M are all residues modulop.

For example, ifp ≡ 1 (mod 8), (mod 12), (mod 5) and (mod 28), then by the law of quadratic reciprocity 2, 3, 5, and 7 will all be residues modulop, and thus all numbers 1–10 will be. The CRT says that this is the same asp ≡ 1 (mod 840), and Dirichlet's theorem says there are an infinite number of primes of this form. 2521 is the smallest, and indeed 1² ≡ 1, 1046² ≡ 2, 123² ≡ 3, 2² ≡ 4, 643² ≡ 5, 87² ≡ 6, 668² ≡ 7, 429² ≡ 8, 3² ≡ 9, and 529² ≡ 10 (mod 2521).

Dirichlet's formulas

The first of these regularities stems fromPeter Gustav Lejeune Dirichlet's work (in the 1830s) on theanalytic formula for theclass number of binaryquadratic forms.^[17] Letq be a prime number,s a complex variable, and define aDirichlet L-function as

L(s)=\sum _{n=1}^{\infty }\left({\frac {n}{q}}\right)n^{-s}.

Dirichlet showed that ifq ≡ 3 (mod 4), then

L(1)=-{\frac {\pi }{\sqrt {q}}}\sum _{n=1}^{q-1}{\frac {n}{q}}\left({\frac {n}{q}}\right)>0.

Therefore, in this case (primeq ≡ 3 (mod 4)), the sum of the quadratic residues minus the sum of the nonresidues in the range 1, 2, ...,q − 1 is a negative number.

For example, modulo 11,
1, 2,3,4,5, 6, 7, 8,9, 10 (residues inbold)
1 + 4 + 9 + 5 + 3 = 22, 2 + 6 + 7 + 8 + 10 = 33, and the difference is −11.

In fact the difference will always be an odd multiple ofq ifq > 3.^[18] In contrast, for primeq ≡ 1 (mod 4), the sum of the quadratic residues minus the sum of the nonresidues in the range 1, 2, ...,q − 1 is zero, implying that both sums equal ${\frac {q(q-1)}{4}}$ .^{[citation needed]}

Dirichlet also proved that for primeq ≡ 3 (mod 4),

L(1)={\frac {\pi }{\left(2-\left({\frac {2}{q}}\right)\right)\!{\sqrt {q}}}}\sum _{n=1}^{\frac {q-1}{2}}\left({\frac {n}{q}}\right)>0.

This implies that there are more quadratic residues than nonresidues among the numbers 1, 2, ..., (q − 1)/2.

For example, modulo 11 there are four residues less than 6 (namely 1, 3, 4, and 5), but only one nonresidue (2).

An intriguing fact about these two theorems is that all known proofs rely on analysis; no-one has ever published a simple or direct proof of either statement.^[19]

Law of quadratic reciprocity

Main article:quadratic reciprocity

Ifp andq are odd primes, then:

((p is a quadratic residue modq) if and only if (q is a quadratic residue modp)) if and only if (at least one ofp andq is congruent to 1 mod 4).

That is:

\left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{{\frac {p-1}{2}}\cdot {\frac {q-1}{2}}}

where $\left({\frac {p}{q}}\right)$ is theLegendre symbol.

Thus, for numbersa and odd primesp that don't dividea:

a	a is a quadratic residue modp if and only if	a	a is a quadratic residue modp if and only if
1	(every primep)	−1	p ≡ 1 (mod 4)
2	p ≡ 1, 7 (mod 8)	−2	p ≡ 1, 3 (mod 8)
3	p ≡ 1, 11 (mod 12)	−3	p ≡ 1 (mod 3)
4	(every primep)	−4	p ≡ 1 (mod 4)
5	p ≡ 1, 4 (mod 5)	−5	p ≡ 1, 3, 7, 9 (mod 20)
6	p ≡ 1, 5, 19, 23 (mod 24)	−6	p ≡ 1, 5, 7, 11 (mod 24)
7	p ≡ 1, 3, 9, 19, 25, 27 (mod 28)	−7	p ≡ 1, 2, 4 (mod 7)
8	p ≡ 1, 7 (mod 8)	−8	p ≡ 1, 3 (mod 8)
9	(every primep)	−9	p ≡ 1 (mod 4)
10	p ≡ 1, 3, 9, 13, 27, 31, 37, 39 (mod 40)	−10	p ≡ 1, 7, 9, 11, 13, 19, 23, 37 (mod 40)
11	p ≡ 1, 5, 7, 9, 19, 25, 35, 37, 39, 43 (mod 44)	−11	p ≡ 1, 3, 4, 5, 9 (mod 11)
12	p ≡ 1, 11 (mod 12)	−12	p ≡ 1 (mod 3)

Pairs of residues and nonresidues

Modulo a primep, the number of pairsn,n + 1 wheren Rp andn + 1 Rp, orn Np andn + 1 Rp, etc., are almost equal. More precisely,^[20]^[21] letp be an odd prime. Fori,j = 0, 1 define the sets

A_{ij}=\left\{k\in \{1,2,\dots ,p-2\}:\left({\frac {k}{p}}\right)=(-1)^{i}\land \left({\frac {k+1}{p}}\right)=(-1)^{j}\right\},

and let

\alpha _{ij}=|A_{ij}|.

That is,

α₀₀ is the number of residues that are followed by a residue,

α₀₁ is the number of residues that are followed by a nonresidue,

α₁₀ is the number of nonresidues that are followed by a residue, and

α₁₁ is the number of nonresidues that are followed by a nonresidue.

Then ifp ≡ 1 (mod 4)

\alpha _{00}={\frac {p-5}{4}},\;\alpha _{01}=\alpha _{10}=\alpha _{11}={\frac {p-1}{4}}

and ifp ≡ 3 (mod 4)

\alpha _{01}={\frac {p+1}{4}},\;\alpha _{00}=\alpha _{10}=\alpha _{11}={\frac {p-3}{4}}.

For example: (residues inbold)
Modulo 17
1,2, 3,4, 5, 6, 7,8,9, 10, 11, 12,13, 14,15,16
A₀₀ = {1,8,15},
A₀₁ = {2,4,9,13},
A₁₀ = {3,7,12,14},
A₁₁ = {5,6,10,11}.
Modulo 19
1, 2, 3,4,5,6,7, 8,9, 10,11, 12, 13, 14, 15,16,17, 18
A₀₀ = {4,5,6,16},
A₀₁ = {1,7,9,11,17},
A₁₀ = {3,8,10,15},
A₁₁ = {2,12,13,14}.

Gauss (1828)^[22] introduced this sort of counting when he proved that ifp ≡ 1 (mod 4) thenx⁴ ≡ 2 (modp) can be solved if and only ifp = a² + 64 b².

The Pólya–Vinogradov inequality

The values of $({\tfrac {a}{p}})$ for consecutive values ofa mimic a random variable like acoin flip.^[23] Specifically,Pólya andVinogradov proved^[24] (independently) in 1918 that for any nonprincipalDirichlet character χ(n) moduloq and any integersM andN,

\left|\sum _{n=M+1}^{M+N}\chi (n)\right|=O\left({\sqrt {q}}\log q\right),

inbig O notation. Setting

\chi (n)=\left({\frac {n}{q}}\right),

this shows that the number of quadratic residues moduloq in any interval of lengthN is

{\frac {1}{2}}N+O({\sqrt {q}}\log q).

It is easy^[25] to prove that

\left|\sum _{n=M+1}^{M+N}\left({\frac {n}{q}}\right)\right|<{\sqrt {q}}\log q.

In fact,^[26]

\left|\sum _{n=M+1}^{M+N}\left({\frac {n}{q}}\right)\right|<{\frac {4}{\pi ^{2}}}{\sqrt {q}}\log q+0.41{\sqrt {q}}+0.61.

Montgomery andVaughan improved this in 1977, showing that, if thegeneralized Riemann hypothesis is true then

\left|\sum _{n=M+1}^{M+N}\chi (n)\right|=O\left({\sqrt {q}}\log \log q\right).

This result cannot be substantially improved, forSchur had proved in 1918 that

\max _{N}\left|\sum _{n=1}^{N}\left({\frac {n}{q}}\right)\right|>{\frac {1}{2\pi }}{\sqrt {q}}

andPaley had proved in 1932 that

\max _{N}\left|\sum _{n=1}^{N}\left({\frac {d}{n}}\right)\right|>{\frac {1}{7}}{\sqrt {d}}\log \log d

for infinitely manyd > 0.

Least quadratic non-residue

The least quadratic residue modp is clearly 1. The question of the magnitude of the least quadratic non-residuen(p) is more subtle, but it is always prime, with 7 appearing for the first time at 71.

The Pólya–Vinogradov inequality above gives O(√p logp).

The best unconditional estimate isn(p) ≪p^θ for any θ>1/4√e, obtained by estimates of Burgess oncharacter sums.^[27]

Assuming theGeneralised Riemann hypothesis, Ankeny obtainedn(p) ≪ (logp)².^[28]

Linnik showed that the number ofp less thanX such thatn(p) > X^ε is bounded by a constant depending on ε.^[27]

The least quadratic non-residues modp for odd primesp are:

2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, ... (sequenceA053760 in theOEIS)

Quadratic excess

Letp be an odd prime. Thequadratic excessE(p) is the number of quadratic residues on the range (0,p/2) minus the number in the range (p/2,p) (sequenceA178153 in theOEIS). Forp congruent to 1 mod 4, the excess is zero, since −1 is a quadratic residue and the residues are symmetric underr ↔p−r. Forp congruent to 3 mod 4, the excessE is always positive.^[29]

Complexity of finding square roots

That is, given a numbera and a modulusn, how hard is it

to tell whether anx solvingx² ≡a (modn) exists
assuming one does exist, to calculate it?

An important difference between prime and composite moduli shows up here. Modulo a primep, a quadratic residuea has 1 + (a|p) roots (i.e. zero ifa Np, one ifa ≡ 0 (modp), or two ifa Rp and gcd(a,p) = 1.)

In general if a composite modulusn is written as a product of powers of distinct primes, and there aren₁ roots modulo the first one,n₂ mod the second, ..., there will ben₁n₂... roots modulon.

The theoretical way solutions modulo the prime powers are combined to make solutions modulon is called theChinese remainder theorem; it can be implemented with an efficient algorithm.^[30]

For example:
Solve x² ≡ 6 (mod 15).
x² ≡ 6 (mod 3) has one solution, 0; x² ≡ 6 (mod 5) has two, 1 and 4.
and there are two solutions modulo 15, namely 6 and 9.
Solve x² ≡ 4 (mod 15).
x² ≡ 4 (mod 3) has two solutions, 1 and 2; x² ≡ 4 (mod 5) has two, 2 and 3.
and there are four solutions modulo 15, namely 2, 7, 8, and 13.
Solve x² ≡ 7 (mod 15).
x² ≡ 7 (mod 3) has two solutions, 1 and 2; x² ≡ 7 (mod 5) has no solutions.
and there are no solutions modulo 15.

Prime or prime power modulus

First off, if the modulusn is prime theLegendre symbol $\left({\frac {a}{n}}\right)$ can bequickly computed using a variation ofEuclid's algorithm^[31] or theEuler's criterion. If it is −1 there is no solution.Secondly, assuming that $\left({\frac {a}{n}}\right)=1$ , ifn ≡ 3 (mod 4),Lagrange found that the solutions are given by

x\equiv \pm \;a^{(n+1)/4}{\pmod {n}},

andLegendre found a similar solution^[32] ifn ≡ 5 (mod 8):

x\equiv {\begin{cases}\pm \;a^{(n+3)/8}{\pmod {n}}&{\text{ if }}a{\text{ is a quartic residue modulo }}n\\\pm \;a^{(n+3)/8}2^{(n-1)/4}{\pmod {n}}&{\text{ if }}a{\text{ is a quartic non-residue modulo }}n\end{cases}}

For primen ≡ 1 (mod 8), however, there is no known formula.Tonelli^[33] (in 1891) andCipolla^[34] found efficient algorithms that work for all prime moduli. Both algorithms require finding a quadratic nonresidue modulon, and there is no efficient deterministic algorithm known for doing that. But since half the numbers between 1 andn are nonresidues, picking numbersx at random and calculating the Legendre symbol $\left({\frac {x}{n}}\right)$ until a nonresidue is found will quickly produce one. A slight variant of this algorithm is theTonelli–Shanks algorithm.

If the modulusn is aprime powern =p^e, a solution may be found modulop and "lifted" to a solution modulon usingHensel's lemma or an algorithm of Gauss.^[8]

Composite modulus

If the modulusn has been factored into prime powers the solution was discussed above.

Ifn is not congruent to 2 modulo 4 and theKronecker symbol $\left({\tfrac {a}{n}}\right)=-1$ then there is no solution; ifn is congruent to 2 modulo 4 and $\left({\tfrac {a}{n/2}}\right)=-1$ , then there is also no solution. Ifn is not congruent to 2 modulo 4 and $\left({\tfrac {a}{n}}\right)=1$ , orn is congruent to 2 modulo 4 and $\left({\tfrac {a}{n/2}}\right)=1$ , there may or may not be one.

If the complete factorization ofn is not known, and $\left({\tfrac {a}{n}}\right)=1$ andn is not congruent to 2 modulo 4, orn is congruent to 2 modulo 4 and $\left({\tfrac {a}{n/2}}\right)=1$ , the problem is known to be equivalent tointeger factorization ofn (i.e. an efficient solution to either problem could be used to solve the other efficiently).

The above discussion indicates how knowing the factors ofn allows us to find the roots efficiently. Say there were an efficient algorithm for finding square roots modulo a composite number. The articlecongruence of squares discusses how finding two numbers x and y wherex² ≡y² (modn) andx ≠ ±y suffices to factorizen efficiently. Generate a random number, square it modulon, and have the efficient square root algorithm find a root. Repeat until it returns a number not equal to the one we originally squared (or its negative modulon), then follow the algorithm described in congruence of squares. The efficiency of the factoring algorithm depends on the exact characteristics of the root-finder (e.g. does it return all roots? just the smallest one? a random one?), but it will be efficient.^[35]

Determining whethera is a quadratic residue or nonresidue modulon (denoteda Rn ora Nn) can be done efficiently for primen by computing the Legendre symbol. However, for compositen, this forms thequadratic residuosity problem, which is not known to be ashard as factorization, but is assumed to be quite hard.

On the other hand, if we want to know if there is a solution forx less than some given limitc, this problem isNP-complete;^[36] however, this is afixed-parameter tractable problem, wherec is the parameter.

In general, to determine ifa is a quadratic residue modulo compositen, one can use the following theorem:^[37]

Letn > 1, andgcd(a,n) = 1. Thenx² ≡a (modn) is solvable if and only if:

TheLegendre symbol $\left({\tfrac {a}{p}}\right)=1$ for all odd prime divisorsp ofn.
a ≡ 1 (mod 4) ifn is divisible by 4 but not 8; ora ≡ 1 (mod 8) ifn is divisible by 8.

Note: This theorem essentially requires that the factorization ofn is known. Also notice that ifgcd(a,n) =m, then the congruence can be reduced toa/m ≡x²/m (modn/m), but then this takes the problem away from quadratic residues (unlessm is a square).

The number of quadratic residues

The list of the number of quadratic residues modulon, forn = 1, 2, 3 ..., looks like:

1, 2, 2, 2, 3, 4, 4, 3, 4, 6, 6, 4, 7, 8, 6, ... (sequenceA000224 in theOEIS)

A formula to count the number of squares modulon is given by Stangl.^[38]

Applications of quadratic residues

Acoustics

Sound diffusers have been based on number-theoretic concepts such asprimitive roots and quadratic residues.^[39]

Graph theory

Paley graphs are dense undirected graphs, one for each primep ≡ 1 (mod 4), that form an infinite family ofconference graphs, which yield an infinite family ofsymmetric conference matrices.

Paley digraphs are directed analogs of Paley graphs, one for eachp ≡ 3 (mod 4), that yieldantisymmetric conference matrices.

The construction of these graphs uses quadratic residues.

Cryptography

The fact that finding a square root of a number modulo a large compositen is equivalent to factoring (which is widely believed to be ahard problem) has been used for constructingcryptographic schemes such as theRabin cryptosystem and theoblivious transfer. Thequadratic residuosity problem is the basis for theGoldwasser-Micali cryptosystem.

Thediscrete logarithm is a similar problem that is also used in cryptography.

Primality testing

Euler's criterion is a formula for the Legendre symbol (a|p) wherep is prime. Ifp is composite the formula may or may not compute (a|p) correctly. TheSolovay–Strassen primality test for whether a given numbern is prime or composite picks a randoma and computes (a|n) using a modification of Euclid's algorithm,^[40] and also using Euler's criterion.^[41] If the results disagree,n is composite; if they agree,n may be composite or prime. For a compositen at least 1/2 the values ofa in the range 2, 3, ...,n − 1 will return "n is composite"; for primen none will. If, after using many different values ofa,n has not been proved composite it is called a "probable prime".

TheMiller–Rabin primality test is based on the same principles. There is a deterministic version of it, but the proof that it works depends on thegeneralized Riemann hypothesis; the output from this test is "n is definitely composite" or "eithern is prime or the GRH is false". If the second output ever occurs for a compositen, then the GRH would be false, which would have implications through many branches of mathematics.

Integer factorization

In § VI of theDisquisitiones Arithmeticae^[42] Gauss discusses two factoring algorithms that use quadratic residues and thelaw of quadratic reciprocity.

Several modern factorization algorithms (includingDixon's algorithm, thecontinued fraction method, thequadratic sieve, and thenumber field sieve) generate small quadratic residues (modulo the number being factorized) in an attempt to find acongruence of squares which will yield a factorization. The number field sieve is the fastest general-purpose factorization algorithm known.

Table of quadratic residues

The following table (sequenceA096008 in theOEIS) lists the quadratic residues mod 1 to 75 (ared number means it is not coprime ton). (For the quadratic residues coprime ton, seeOEIS: A096103, and for nonzero quadratic residues, seeOEIS: A046071.)

n	quadratic residues modn	n	quadratic residues modn	n	quadratic residues modn
1	0	26	0, 1, 3,4, 9,10,12,13,14,16, 17,22, 23, 25	51	0, 1, 4,9, 13,15, 16,18, 19,21, 25,30,33,34,36,42, 43, 49
2	0, 1	27	0, 1, 4, 7,9, 10, 13, 16, 19, 22, 25	52	0, 1,4, 9,12,13,16, 17, 25, 29,36,40,48, 49
3	0, 1	28	0, 1,4,8, 9,16,21, 25	53	0, 1, 4, 6, 7, 9, 10, 11, 13, 15, 16, 17, 24, 25, 28, 29, 36, 37, 38, 40, 42, 43, 44, 46, 47, 49, 52
4	0, 1	29	0, 1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 28	54	0, 1,4, 7,9,10, 13,16, 19,22, 25,27,28, 31,34,36, 37,40, 43,46, 49,52
5	0, 1, 4	30	0, 1,4,6,9,10,15,16, 19,21,24,25	55	0, 1, 4,5, 9,11, 14,15, 16,20,25, 26, 31, 34, 36,44,45, 49
6	0, 1,3,4	31	0, 1, 2, 4, 5, 7, 8, 9, 10, 14, 16, 18, 19, 20, 25, 28	56	0, 1,4,8, 9,16, 25,28,32,36,44,49
7	0, 1, 2, 4	32	0, 1,4, 9,16, 17, 25	57	0, 1, 4,6, 7,9, 16,19,24, 25, 28,30,36,39,42, 43,45, 49,54, 55
8	0, 1,4	33	0, 1,3, 4,9,12,15, 16,22, 25,27, 31	58	0, 1,4, 5,6, 7, 9, 13,16,20,22, 23,24, 25,28,29,30, 33,34, 35,36,38,42, 45, 49, 51,52, 53,54, 57
9	0, 1, 4, 7	34	0, 1,2,4,8, 9, 13, 15,16,17,18, 19, 21, 25,26,30,32, 33	59	0, 1, 3, 4, 5, 7, 9, 12, 15, 16, 17, 19, 20, 21, 22, 25, 26, 27, 28, 29, 35, 36, 41, 45, 46, 48, 49, 51, 53, 57
10	0, 1,4,5,6, 9	35	0, 1, 4, 9, 11,14,15, 16,21,25, 29,30	60	0, 1,4,9,16,21,24,25,36,40,45, 49
11	0, 1, 3, 4, 5, 9	36	0, 1,4,9, 13,16, 25,28	61	0, 1, 3, 4, 5, 9, 12, 13, 14, 15, 16, 19, 20, 22, 25, 27, 34, 36, 39, 41, 42, 45, 46, 47, 48, 49, 52, 56, 57, 58, 60
12	0, 1,4,9	37	0, 1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36	62	0, 1,2,4, 5, 7,8, 9,10,14,16,18, 19,20, 25,28,31,32, 33, 35,36,38, 39,40, 41, 45, 47, 49,50, 51,56, 59
13	0, 1, 3, 4, 9, 10, 12	38	0, 1,4, 5,6, 7, 9, 11,16, 17,19,20, 23,24, 25,26,28,30, 35,36	63	0, 1, 4,7,9, 16,18, 22, 25,28,36, 37, 43, 46,49, 58
14	0, 1,2,4,7,8, 9, 11	39	0, 1,3, 4,9, 10,12,13, 16, 22, 25,27,30,36	64	0, 1,4, 9,16, 17, 25, 33,36, 41, 49, 57
15	0, 1, 4,6,9,10	40	0, 1,4, 9,16,20,24,25,36	65	0, 1, 4, 9,10, 14, 16,25,26, 29,30,35, 36,39,40, 49, 51,55, 56, 61, 64
16	0, 1,4, 9	41	0, 1, 2, 4, 5, 8, 9, 10, 16, 18, 20, 21, 23, 25, 31, 32, 33, 36, 37, 39, 40	66	0, 1,3,4,9,12,15,16,22, 25,27, 31,33,34,36, 37,42,45,48, 49,55,58,60,64
17	0, 1, 2, 4, 8, 9, 13, 15, 16	42	0, 1,4,7,9,15,16,18,21,22, 25,28,30,36, 37,39	67	0, 1, 4, 6, 9, 10, 14, 15, 16, 17, 19, 21, 22, 23, 24, 25, 26, 29, 33, 35, 36, 37, 39, 40, 47, 49, 54, 55, 56, 59, 60, 62, 64, 65
18	0, 1,4, 7,9,10, 13,16	43	0, 1, 4, 6, 9, 10, 11, 13, 14, 15, 16, 17, 21, 23, 24, 25, 31, 35, 36, 38, 40, 41	68	0, 1,4,8, 9, 13,16,17, 21, 25,32, 33,36, 49,52, 53,60,64
19	0, 1, 4, 5, 6, 7, 9, 11, 16, 17	44	0, 1,4, 5, 9,12,16,20, 25,33,36, 37	69	0, 1,3, 4,6,9,12, 13, 16,18,24, 25,27, 31,36,39,46,48, 49, 52,54, 55, 58, 64
20	0, 1,4,5, 9,16	45	0, 1, 4,9,10, 16, 19,25, 31, 34,36,40	70	0, 1,4, 9, 11,14,15,16,21,25, 29,30,35,36, 39,44,46,49,50, 51,56,60,64,65
21	0, 1, 4,7,9,15, 16,18	46	0, 1,2, 3,4,6,8, 9,12, 13,16,18,23,24, 25,26, 27, 29, 31,32, 35,36, 39, 41	71	0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 19, 20, 24, 25, 27, 29, 30, 32, 36, 37, 38, 40, 43, 45, 48, 49, 50, 54, 57, 58, 60, 64
22	0, 1, 3,4, 5, 9,11,12,14, 15,16,20	47	0, 1, 2, 3, 4, 6, 7, 8, 9, 12, 14, 16, 17, 18, 21, 24, 25, 27, 28, 32, 34, 36, 37, 42	72	0, 1,4,9,16, 25,28,36,40, 49,52,64
23	0, 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18	48	0, 1,4,9,16, 25,33,36	73	0, 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 19, 23, 24, 25, 27, 32, 35, 36, 37, 38, 41, 46, 48, 49, 50, 54, 55, 57, 61, 64, 65, 67, 69, 70, 71, 72
24	0, 1,4,9,12,16	49	0, 1, 2, 4, 8, 9, 11, 15, 16, 18, 22, 23, 25, 29, 30, 32, 36, 37, 39, 43, 44, 46	74	0, 1, 3,4, 7, 9,10, 11,12,16, 21, 25,26, 27,28,30, 33,34,36,37,38,40, 41,44,46, 47,48, 49, 53,58,62, 63,64, 65, 67,70, 71, 73
25	0, 1, 4, 6, 9, 11, 14, 16, 19, 21, 24	50	0, 1,4,6, 9, 11,14,16, 19, 21,24,25,26, 29, 31,34,36, 39, 41,44,46, 49	75	0, 1, 4,6,9, 16, 19,21,24,25, 31, 34,36,39, 46, 49,51,54, 61, 64,66,69

Quadratic Residues (see alsoA048152,A343720)
x	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
x²	1	4	9	16	25	36	49	64	81	100	121	144	169	196	225	256	289	324	361	400	441	484	529	576	625
mod 1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
mod 2	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
mod 3	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1
mod 4	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
mod 5	1	4	4	1	0	1	4	4	1	0	1	4	4	1	0	1	4	4	1	0	1	4	4	1	0
mod 6	1	4	3	4	1	0	1	4	3	4	1	0	1	4	3	4	1	0	1	4	3	4	1	0	1
mod 7	1	4	2	2	4	1	0	1	4	2	2	4	1	0	1	4	2	2	4	1	0	1	4	2	2
mod 8	1	4	1	0	1	4	1	0	1	4	1	0	1	4	1	0	1	4	1	0	1	4	1	0	1
mod 9	1	4	0	7	7	0	4	1	0	1	4	0	7	7	0	4	1	0	1	4	0	7	7	0	4
mod 10	1	4	9	6	5	6	9	4	1	0	1	4	9	6	5	6	9	4	1	0	1	4	9	6	5
mod 11	1	4	9	5	3	3	5	9	4	1	0	1	4	9	5	3	3	5	9	4	1	0	1	4	9
mod 12	1	4	9	4	1	0	1	4	9	4	1	0	1	4	9	4	1	0	1	4	9	4	1	0	1
mod 13	1	4	9	3	12	10	10	12	3	9	4	1	0	1	4	9	3	12	10	10	12	3	9	4	1
mod 14	1	4	9	2	11	8	7	8	11	2	9	4	1	0	1	4	9	2	11	8	7	8	11	2	9
mod 15	1	4	9	1	10	6	4	4	6	10	1	9	4	1	0	1	4	9	1	10	6	4	4	6	10
mod 16	1	4	9	0	9	4	1	0	1	4	9	0	9	4	1	0	1	4	9	0	9	4	1	0	1
mod 17	1	4	9	16	8	2	15	13	13	15	2	8	16	9	4	1	0	1	4	9	16	8	2	15	13
mod 18	1	4	9	16	7	0	13	10	9	10	13	0	7	16	9	4	1	0	1	4	9	16	7	0	13
mod 19	1	4	9	16	6	17	11	7	5	5	7	11	17	6	16	9	4	1	0	1	4	9	16	6	17
mod 20	1	4	9	16	5	16	9	4	1	0	1	4	9	16	5	16	9	4	1	0	1	4	9	16	5
mod 21	1	4	9	16	4	15	7	1	18	16	16	18	1	7	15	4	16	9	4	1	0	1	4	9	16
mod 22	1	4	9	16	3	14	5	20	15	12	11	12	15	20	5	14	3	16	9	4	1	0	1	4	9
mod 23	1	4	9	16	2	13	3	18	12	8	6	6	8	12	18	3	13	2	16	9	4	1	0	1	4
mod 24	1	4	9	16	1	12	1	16	9	4	1	0	1	4	9	16	1	12	1	16	9	4	1	0	1
mod 25	1	4	9	16	0	11	24	14	6	0	21	19	19	21	0	6	14	24	11	0	16	9	4	1	0

Notes

^Lemmemeyer, Ch. 1
^Lemmermeyer, pp 6–8, p. 16 ff
^Gauss, DA, art. 94
^^a ^bGauss, DA, art. 96
^^a ^bGauss, DA, art. 98
^Gauss, DA, art 111
^Gauss, DA, art. 103
^^a ^bGauss, DA, art. 101
^Gauss, DA, art. 102
^e.g.,Ireland & Rosen 1990, p. 50
^Gauss, DA, art. 131
^e.g. Hardy and Wright use it
^Gauss, DA, art 230 ff.
^This extension of the domain is necessary for definingL functions.
^SeeLegendre symbol#Properties of the Legendre symbol for examples
^Lemmermeyer, pp 111–end
^Davenport 2000, pp. 8–9, 43–51. These are classical results.
^Davenport 2000, pp. 49–51, (conjectured byJacobi, proved by Dirichlet)
^Davenport 2000, p. 9
^Lemmermeyer, p. 29 ex. 1.22; cf pp. 26–27, Ch. 10
^Crandall & Pomerance, ex 2.38, pp 106–108
^Gauss,Theorie der biquadratischen Reste, Erste Abhandlung (pp 511–533 of theUntersuchungen über hohere Arithmetik)
^Crandall & Pomerance, ex 2.38, pp 106–108 discuss the similarities and differences. For example, tossingn coins, it is possible (though unlikely) to getn/2 heads followed by that many tails. V-P inequality rules that out for residues.
^Davenport 2000, pp. 135–137, (proof of P–V, (in fact big-O can be replaced by 2); journal references for Paley, Montgomery, and Schur)
^Planet Math: Proof of Pólya–Vinogradov Inequality inexternal links. The proof is a page long and only requires elementary facts about Gaussian sums
^Pomerance & Crandall, ex 2.38 pp.106–108. result from T. Cochrane, "On a trigonometric inequality of Vinogradov",J. Number Theory, 27:9–16, 1987
^^a ^bFriedlander, John B.;Iwaniec, Henryk (2010).Opera De Cribro.American Mathematical Society. p. 156.ISBN 978-0-8218-4970-5.Zbl 1226.11099.
^Montgomery, Hugh L. (1994).Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis.American Mathematical Society. p. 176.ISBN 0-8218-0737-4.Zbl 0814.11001.
^Bateman, Paul T.; Diamond, Harold G. (2004).Analytic Number Theory. World Scientific. p. 250.ISBN 981-256-080-7.Zbl 1074.11001.
^Bach & Shallit 1996, p. 104 ff; it requires O(log²m) steps wherem is the number of primes dividingn.
^Bach & Shallit 1996, p. 113; computing $\left({\frac {a}{n}}\right)$ requires O(loga logn) steps
^Lemmermeyer, p. 29
^Bach & Shallit 1996, p. 156 ff; the algorithm requires O(log⁴n) steps.
^Bach & Shallit 1996, p. 156 ff; the algorithm requires O(log³n) steps and is also nondeterministic.
^Crandall & Pomerance, ex. 6.5 & 6.6, p.273
^Manders & Adleman 1978
^Burton, David (2007).Elementary Number Theory. New York: McGraw HIll. p. 195.
^Stangl, Walter D. (October 1996),"Counting Squares in ℤ_n"(PDF),Mathematics Magazine,69 (4):285–289,doi:10.2307/2690536,JSTOR 2690536
^Walker, R."The design and application of modular acoustic diffusing elements"(PDF). BBC Research Department. Retrieved25 October 2016.
^Bach & Shallit 1996, p. 113
^Bach & Shallit 1996, pp. 109–110; Euler's criterion requires O(log³n) steps
^Gauss, DA, arts 329–334

References

TheDisquisitiones Arithmeticae has been translated from Gauss'sCiceronian Latin intoEnglish andGerman. The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of theGauss sum, the investigations intobiquadratic reciprocity, and unpublished notes.

Gauss, Carl Friedrich (1986),Disquisitiones Arithemeticae, translated by Clarke, Arthur A. (Second corrected ed.), New York:Springer,ISBN 0-387-96254-9
Gauss, Carl Friedrich (1965),Untersuchungen über hohere Arithmetik [Disquisitiones Arithemeticae & other papers on number theory], translated by Maser, H. (second ed.), New York: Chelsea,ISBN 0-8284-0191-8
Bach, Eric; Shallit, Jeffrey (1996),Efficient Algorithms, Algorithmic Number Theory, vol. I, Cambridge:The MIT Press,ISBN 0-262-02405-5
Crandall, Richard; Pomerance, Carl (2001),Prime Numbers: A Computational Perspective, New York: Springer,ISBN 0-387-94777-9
Davenport, Harold (2000),Multiplicative Number Theory (third ed.), New York: Springer,ISBN 0-387-95097-4
Garey, Michael R.;Johnson, David S. (1979),Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman,ISBN 0-7167-1045-5 A7.1: AN1, pg.249.
Hardy, G. H.;Wright, E. M. (1980),An Introduction to the Theory of Numbers (fifth ed.), Oxford:Oxford University Press,ISBN 978-0-19-853171-5
Ireland, Kenneth; Rosen, Michael (1990),A Classical Introduction to Modern Number Theory (second ed.), New York: Springer,ISBN 0-387-97329-X
Lemmermeyer, Franz (2000),Reciprocity Laws: from Euler to Eisenstein, Berlin: Springer,ISBN 3-540-66957-4
Manders, Kenneth L.;Adleman, Leonard (1978), "NP-Complete Decision Problems for Binary Quadratics",Journal of Computer and System Sciences,16 (2):168–184,doi:10.1016/0022-0000(78)90044-2.

External links

v t e Number theory
Fields	Algebraic number theory (class field theory,non-abelian class field theory,Iwasawa theory,Iwasawa–Tate theory,Kummer theory) Analytic number theory (analytic theory of L-functions,probabilistic number theory,sieve theory) Geometric number theory Computational number theory Transcendental number theory Diophantine geometry (Arakelov theory,Hodge–Arakelov theory) Arithmetic combinatorics (additive number theory) Arithmetic geometry (anabelian geometry,p-adic Hodge theory) Arithmetic topology Arithmetic dynamics
Key concepts	Numbers 0 Natural numbers Unity Prime numbers Composite numbers Rational numbers Irrational numbers Algebraic numbers Transcendental numbers p-adic numbers (p-adic analysis) Arithmetic Modular arithmetic Chinese remainder theorem Arithmetic functions
Advanced concepts	Quadratic forms Modular forms L-functions Diophantine equations Diophantine approximation Irrationality measure Simple continued fractions
Category List of topics List of recreational topics Wikibook Wikiversity

v t e Polynomials andpolynomial functions
Bydegree	Zero polynomial (degree undefined or −1 or −∞) Constant function (0) Linear function (1) Linear equation Quadratic function (2) Quadratic equation Cubic function (3) Cubic equation Quartic function (4) Quartic equation Quintic function (5) Sextic equation (6) Septic equation (7)
By properties	Univariate Bivariate Multivariate Monomial Binomial Trinomial Irreducible Square-free Homogeneous Quasi-homogeneous
Tools and algorithms	Factorization Greatest common divisor Division Horner's method of evaluation Polynomial identity testing Resultant Discriminant Gröbner basis

v t e Geometry
History Timeline Lists
Euclidean geometry	Combinatorial Convex Discrete Plane geometry Polygon Polyform Solid geometry
Non-Euclidean geometry	Elliptic Hyperbolic Symplectic Spherical Affine Projective Riemannian
Other	Trigonometry Lie group Algebraic geometry Differential geometry
Lists	Shape Lists List of geometry topics List of differential geometry topics
Category

v t e Algebra
Outline History
Areas	Abstract algebra Algebraic geometry Algebraic variety Scheme Algebraic number theory Category theory Commutative algebra Elementary algebra Homological algebra K-theory Linear algebra Multilinear algebra Noncommutative algebra Order theory Representation theory Universal algebra
Basic concepts	Algebraic expression Equation (Linear equation,Quadratic equation) Function (Polynomial function) Inequality (Linear inequality) Operation (Addition,Multiplication) Relation (Equivalence relation) Variable
Algebraic structures	Field (theory) Group (theory) Module (theory) Ring (theory) Vector space (Vector)
Linear and multilinear algebra	Basis Determinant Eigenvalues and eigenvectors Inner product space (Dot product) Hilbert space Linear map (Matrix) Linear subspace (Affine space) Norm (Euclidean norm) Orthogonality (Orthogonal complement) Rank Trace
Algebraic constructions	Composition algebra Exterior algebra Free object (Free group, ...) Geometric algebra (Multivector) Polynomial ring (Polynomial) Quotient object (Quotient group, ...) Symmetric algebra Tensor algebra
Topic lists	Algebraic structures
Glossaries	Field theory Linear algebra Order theory Ring theory
Category