 Quadratic residue

In number theory, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that:
Otherwise, q is called a quadratic nonresidue modulo n.
Originally an abstract mathematical concept from the branch of number theory known as modular arithmetic, quadratic residues are now used in applications ranging from acoustical engineering to cryptography and the factoring of large numbers.
Contents
History, conventions, and elementary facts
Fermat, Euler, Lagrange, Legendre, and other number theorists of the 17th and 18th centuries proved some theorems^{[1]} and made some conjectures^{[2]} about quadratic residues, but the first systematic treatment is § IV of Gauss's Disquisitiones Arithmeticae (1801). Article 95 introduces the terminology "quadratic residue" and "quadratic nonresidue", and states that, if the context makes it clear, the adjective "quadratic" may be dropped.
For a given n a list of the quadratic residues modulo n may be obtained by simply squaring the numbers 0, 1, …, n − 1. Because a^{2} ≡ (n − a)^{2} (mod n), the list of squares modulo n is symmetrical around n/2, and the list only needs to go that high. This can be seen in the table at the end of the article.
Thus, the number of quadratic residues modulo n cannot exceed n/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 odd prime number p there are (p + 1)/2 residues (including 0) and (p − 1)/2 nonresidues. In this case, it is customary to consider 0 as a special case and work within the multiplicative group of nonzero elements of the field Z/pZ. (In other words, every congruence class except zero modulo p 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 a prime number there are 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 the law of quadratic reciprocity is that if p ≡ 1 (mod 4) then −1 is a quadratic residue modulo p, and if p ≡ 3 (mod 4) then −1 is a nonresidue modulo p. This implies
If p ≡ 1 (mod 4) the negative of a residue modulo p is a residue and the negative of a nonresidue is a nonresidue.
If p ≡ 3 (mod 4) the negative of a residue modulo p is a nonresidue and the negative of a nonresidue is a residue.
Prime power modulus
All odd squares are ≡ 1 (mod 8) and a fortiori ≡ 1 (mod 4). If a is an odd number and m = 8, 16, or some higher power of 2, then a is a residue modulo m if and only if a ≡ 1 (mod 8).^{[7]}
For example, mod (32) the odd squares are
 1^{2} ≡ 15^{2} ≡ 1
 3^{2} ≡ 13^{2} ≡ 9
 5^{2} ≡ 11^{2} ≡ 25
 7^{2} ≡ 9^{2} ≡ 17
 0^{2} ≡ 8^{2} ≡ 16^{2} ≡ 0
 2^{2} ≡ 6^{2}≡ 10^{2} ≡ 14^{2}≡ 4
 4^{2} ≡ 12^{2} ≡ 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 number A relatively prime to an odd prime p is a residue modulo any power of p if and only if it is a residue modulo p.^{[8]}
If the modulus is p^{n},
 then p^{k}A
 is a residue modulo p^{n} if k ≥ n
 is a nonresidue modulo p^{n} if k < n is odd
 is a residue modulo p^{n} if k < n is even and A is a residue
 is a nonresidue modulo p^{n} if k < n is even and A is a nonresidue.^{[9]}
Notice that the rules are different for powers of two and powers of odd primes.
Modulo an odd prime power n = p^{k}, the products of residues and nonresidues relatively prime to p obey the same rules as they do mod p; 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 of p 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 nonresidues and 1 form the Klein fourgroup.
Composite modulus not a prime power
The basic fact in this case is
 if a is a residue modulo n, then a is a residue modulo p^{k} for every prime power dividing n.
 if a is a nonresidue modulo n, then a is a nonresidue modulo p^{k} for at least one prime power dividing n.
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 in bold). 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 in bold). 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 a group under multiplication, called the group of units of the ring Z/nZ, and the squares are a subgroup of it. Different nonresidues may belong to different cosets, 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 Z/nZ, which has zero divisors for composite n.
For this reason some authors^{[10]} add to the definition that a quadratic residue q must not only be a square but must also be relatively prime to the modulus n.
Although it makes things tidier, this article does not insist that residues must be coprime to the modulus.
Notations
Gauss^{[11]} used R and N to denote residuacity and nonresiduacity, respectively;
 for example, 2 R 7 and 5 N 7, or 1 R 8 and 3,5,7 N 8.
Although this notation is compact and convenient for some purposes,^{[12]}^{[13]} the most useful notation is the Legendre symbol, also called the quadratic character, which is defined for all integers a and positive odd prime numbers p as
There are two reasons why numbers ≡ 0 (mod p) 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 a homomorphism from the multiplicative group of nonzero conguence classes modulo p to the complex numbers. Setting allows its domain to be extended to the multiplicative semigroup 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 to cubic, quartic and higher power residues.^{[16]}
There is a generalization of the Legendre symbol for composite values of p, the Jacobi symbol, but its properties are not as simple: if m is composite and the Jacobi symbol then a N m, and if a R m then but if we do not know whether a R m or a N m. If m is prime, the Jacobi and Legendre symbols agree.
Distribution of quadratic residues
Although quadratic residues appear to occur in a rather random pattern modulo n, and this has been exploited in such applications as acoustics and cryptography, their distribution also exhibits some striking regularities.
Using Dirichlet's theorem on primes in arithmetic progressions, the law of quadratic reciprocity, and the Chinese remainder theorem (CRT) it is easy to see that for any M > 0 there are primes p such that the numbers 1, 2, …, M are all residues modulo p.
For example, if p ≡ 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 modulo p, and thus all numbers 1–10 will be. The CRT says that this is the same as p ≡ 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^{2} ≡ 1, 1046^{2} ≡ 2, 123^{2} ≡ 3, 2^{2} ≡ 4, 643^{2} ≡ 5, 87^{2} ≡ 6, 668^{2} ≡ 7, 429^{2} ≡ 8, 3^{2} ≡ 9, and 529^{2} ≡ 10 (mod 2521).
Dirichlet's formulas
The first of these regularities stems from Dirichlet's work (in the 1830s) on the analytic formula for the class number of binary quadratic forms.^{[17]} Let q be a prime number, s a complex variable, and define a Dirichlet Lfunction as
Dirichlet showed that if q ≡ 3 (mod 4), then
Therefore, in this case (prime q ≡ 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 in bold)
 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 of q if q > 3.^{[18]} In contrast, for prime q ≡ 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 . Dirichlet also proved that for prime q ≡ 3 (mod 4),
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; noone has ever published a simple or direct proof of either statement.^{[19]}
Pairs of residues and nonresidues
Modulo a prime p, the number of pairs n, n + 1 where n R p and n + 1 R p, or n N p and n + 1 R p, etc., are almost equal. More precisely,^{[20]}^{[21]}
Let p be an odd prime. For i, j = 0, 1 define the sets
and let
 α_{ij} =  A_{ij}  .
That is,
 α_{00} is the number of residues that are followed by a residue,
 α_{01} is the number of residues that are followed by a nonresidue,
 α_{10} is the number of nonresidues that are followed by a residue, and
 α_{11} is the number of nonresidues that are followed by a nonresidue.
Then if p ≡ 1 (mod 4)
and if p ≡ 3 (mod 4)
For example: (residues in bold) Modulo 17
 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
 A_{00} = {1,8,15},
 A_{01} = {2,4,9,13},
 A_{10} = {3,7,12,14},
 A_{11} = {5,6,10,11}.
 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18
 A_{00} = {4,5,6,16},
 A_{01} = {1,7,9,11,17},
 A_{10} = {3,8,10,15},
 A_{11} = {2,12,13,14}.
Gauss (1828)^{[22]} introduced this sort of counting when he proved that if p ≡ 1 (mod 4) then x^{4} ≡ 2 (mod p) can be solved if and only if p = a^{2} + 64 b^{2}.
The Pólya–Vinogradov inequality
The values of for consecutive values of a mimic a random variable like a coin flip.^{[23]} Specifically,
Pólya and Vinogradov proved^{[24]} (independently) in 1918 that for any nonprincipal Dirichlet character χ(n) modulo q and any integers M and N, in big O notation. Setting
this shows that the number of quadratic residues modulo q in any interval of length N is
 It is easy^{[25]} to prove that
In fact,^{[26]}
Montgomery and Vaughan improved this in 1977, showing that, if the generalized Riemann hypothesis is true then
This result cannot be substantially improved, for Schur had proved in 1918 that
and Paley had proved in 1932 that
for infinitely many d > 0.
Complexity of finding square roots
That is, given a number a and a modulus n, how hard is it
 to tell whether an x solving x^{2} ≡ a (mod n) exists
 assuming one does exist, to calculate it?
An important difference between prime and composite moduli shows up here. Modulo a prime p, a quadratic residue a has 1 + (ap) roots (i.e. zero if a N p, one if a ≡ 0 (mod p), or two if a R p and gcd(a,p) = 1.)
In general if a composite modulus n is written as a product of powers of distinct primes, and there are n_{1} roots modulo the first one, n_{2} mod the second, …, there will be n_{1}n_{2}… roots modulo n.
The theoretical way solutions modulo the prime powers are combined to make solutions modulo n is called the Chinese remainder theorem; it can be implemented with an efficient algorithm.^{[27]}
For example:
 Solve x^{2} ≡ 6 (mod 15).
 x^{2} ≡ 6 (mod 3) has one solution, 0; x^{2} ≡ 6 (mod 5) has two, 1 and 4.
 and there are two solutions modulo 15, namely 6 and 9.
 Solve x^{2} ≡ 4 (mod 15).
 x^{2} ≡ 4 (mod 3) has two solutions, 1 and 2; x^{2} ≡ 4 (mod 5) has two, 2 and 3.
 and there are four solutions modulo 15, namely 2, 7, 8, and 13.
Prime or prime power modulus
First off, if the modulus n is prime the Legendre symbol (an) can be quickly computed using a variation of Euclid's algorithm.;^{[28]} if it is −1 there is no solution. Secondly, assuming that (an) = 1, if n ≡ 3 (mod 4), Lagrange found that the solutions are given by
and Legendre found a similar solution^{[29]} if n ≡ 5 (mod 8).
For prime n ≡ 1 (mod 8), however, there is no known formula. Tonelli^{[30]} (in 1891) and Cipolla^{[31]} found efficient algorithms that work for all prime moduli. Both algorithms require finding a quadratic nonresidue modulo n, and there is no efficient deterministic algorithm known for doing that. But since half the numbers between 1 and n are nonresidues, picking numbers x at random and calculating the Legendre symbol (xn) until a nonresidue is found will quickly produce one.
If the modulus n is a prime power n = p^{e}, a solution may be found modulo p and "lifted" to a solution modulo n using Hensel's lemma or an algorithm of Gauss.^{[8]}
Composite modulus
If the modulus n has been factored into prime powers the solution was discussed above.
If the Jacobi symbol (an) = −1 then there is no solution. If it is +1, there may or may not be one.
If the factorization of n is not known, and (an) = 1, the problem is known to be equivalent to integer factorization of n (i.e. an efficient solution to either problem could be used to solve the other efficiently).
The above discussion indicates how knowing the factors of n allows us to find the roots efficiently. Say there were an efficient algorithm for finding square roots modulo a composite number. The article congruence of squares discusses how finding two numbers x and y where x^{2} ≡ y^{2} (mod n) and x ≠ ±y suffices to factorize n efficiently. Generate a random number, square it modulo n, 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 modulo n), then follow the algorithm described in congruence of squares. The efficiency of the factoring algorithm depends on the exact characteristics of the rootfinder (e.g. does it return all roots? just the smallest one? a random one?), but it will be efficient.^{[32]}
Simply determining whether a N n or a R n (which can be done efficiently for prime n by computing the Legendre symbol) is known as the quadratic residuosity problem when n is composite. It is not known to be as hard as factorization, but is thought to be quite hard.
On the other hand, if we want to know if there is a solution for x less than some given limit c, this problem is NPcomplete;^{[33]} however, this is a fixedparameter tractable problem, where c is the parameter.
In general, to determine if a quadratic congruence with composite modulus is solvable use the following theorem^{[34]} :Let n > 1, and gcd(a,n) =1. Then x^{2} ≡ a (mod n) is solvable if and only if:
a) The Legendre symbol, (a/p) = 1 for all odd prime divisors of n.
b) a = 1 (mod 4) if 4n, but 8 does not divide n; a ≡ 1 (mod 8) if 8n.
Note: This theorem essentially requires that the factorization of n is known. Also notice that if gcd(a,n)=m, then the congruence can be reduced to a/m ≡ x^{2}/m (mod n/m), but then this takes the problem away from being a problem of quadratic congruences (unless m is a square).
Applications of quadratic residues
Acoustics
Sound diffusers have been based on numbertheoretic concepts such as primitive roots and quadratic residues.
Graph theory
Paley graphs are dense undirected graphs, one for each prime p ≡ 1 (mod 4), that form an infinite family of conference graphs, which yield an infinite family of symmetric conference matrices.
Paley digraphs are directed analogs of Paley graphs, one for each p ≡ 3 (mod 4), that yield antisymmetric conference matrices.
The construction of these graphs uses quadratic residues.
Cryptography
The fact that finding a square root of a number modulo a large composite n is equivalent to factoring (which is widely believed be a hard problem) has been used for constructing cryptographic schemes such as the Rabin cryptosystem and the oblivious transfer. The quadratic residuosity problem is the basis for the GoldwasserMicali cryptosystem.
The discrete logarithm is a similar problem that is also used in cryptography.
Primality testing
Euler's criterion is a formula for the Legendre symbol (ap) where p is prime. If p is composite the formula may or may not compute (ap) correctly. The SolovayStrassen primality test for whether a given number n is prime or composite picks a random a and computes (an) using a modification of Euclid's algorithm,^{[35]} and also using Euler's criterion.^{[36]} If the results disagree, n is composite; if they agree, n may be composite or prime. For a composite n at least 1/2 the values of a in the range 2, 3, ..., n − 1 will return "n is composite"; for prime n none will. If, after using many different values of a, n has not been proved composite it is called a "probable prime".
The MillerRabin primality test is based on the same principles. There is a deterministic version of it, but the proof that it works depends on the generalized Riemann hypothesis; the output from this test is "n is definitely composite" or "either n is prime or the GRH is false". If the second output ever occurs for a composite n, then the GRH would be false, which would have implications through many branches of mathematics.
Integer factorization
In § VI of the Disquisitiones Arithmeticae^{[37]} Gauss discusses two factoring algorithms that use quadratic residues and the law of quadratic reciprocity.
Several modern factorization algorithms (including Dixon's algorithm, the continued fraction method, the quadratic sieve, and the number field sieve) generate small quadratic residues (modulo the number being factorized) in an attempt to find a congruence of squares which will yield a factorization. The number field sieve is the fastest generalpurpose factorization algorithm known.
Table of quadratic residues
Quadratic Residues 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^{2} 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 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 See also
 Euler's criterion
 Gauss's lemma
 Zolotarev's lemma
 Character sum
 Law of quadratic reciprocity
 Quadratic residue code
Notes
 ^ Lemmemeyer, Ch. 1
 ^ Lemmermeyer, pp 6–8, p. 16 ff
 ^ Gauss, DA, art. 94
 ^ ^{a} ^{b} Gauss, DA, art. 96
 ^ ^{a} ^{b} Gauss, DA, art. 98
 ^ Gauss, DA, art 111
 ^ Gauss, DA, art. 103
 ^ ^{a} ^{b} Gauss, DA, art. 101
 ^ Gauss, DA, art. 102
 ^ e.g. Ireland & Rosen, 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 defining L functions.
 ^ See Legendre symbol#Formulas for the Legendre symbol for examples
 ^ Lemmermeyer, pp 111–end
 ^ Davenport, pp 8–9, 43–51. These are classical results.
 ^ Davenport, pp 49–51 (conjectured by Jacobi, proved by Dirichlet)
 ^ Davenport, 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 the Untersuchungen über hohere Arithmetik)
 ^ Crandall & Pomerance, ex 2.38, pp 106–108 discuss the similarities and differences. For example, tossing n coins, it is possible (though unlikely) to get n/2 heads followed by that many tails. VP inequality rules that out for residues.
 ^ Davenport, pp 135137 (proof of P–V, (in fact bigO can be replace by 2); journal references for Paley, Montgomery, and Schur)
 ^ Planet Math: Proof of Pólya–Vinogradov Inequality in external 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
 ^ Bach & Shallit, p 104 ff; it requires O(log^{2} m) steps where m is the number of primes dividing n.
 ^ Bach & Shallit p 113; computing (an) requires O(log a log n) steps
 ^ Lemmermeyer, p. 29
 ^ Bach & Shallit p. 156 ff; the algorithm requires O(log^{4}n) steps.
 ^ Bach & Shallit p. 156 ff; the algorithm requires O(log^{3} n) steps and is also nondetermisitic.
 ^ Crandall & Pomerance, ex. 6.5 & 6.6, p.273
 ^ Manders & Adleman 1978
 ^ Burton, David (2007). Elementary Number Theory. New York: McGraw HIll. pp. 195.
 ^ Bach & Shallit p 113
 ^ Bach & Shallit pp 109–110; Euler's criterion requires O(log^{3} n) steps
 ^ Gauss, DA, arts 329–334
References
The Disquisitiones Arithmeticae has been translated from Gauss's Ciceronian Latin into English and German. The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.
 Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English) (1986), Disquisitiones Arithemeticae (Second, corrected edition), New York: Springer, ISBN 0387962549
 Gauss, Carl Friedrich; Maser, H. (translator into German) (1965), Untersuchungen über hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition), New York: Chelsea, ISBN 0828401918
 Bach, Eric; Shallit, Jeffrey (1996), Algorithmic Number Theory (Vol I: Efficient Algorithms), Cambridge: The MIT Press, ISBN 0262024055
 Crandall, Richard; Pomerance, Carl (2001), Prime Numbers: A Computational Perspective, New York: Springer, ISBN 0387047779
 Davenport, Harold (2000), Multiplicative Number Theory (Third edition), New York: Springer, ISBN 0387950974
 Michael R. Garey and David S. Johnson (1979), Computers and Intractability: A Guide to the Theory of NPCompleteness, W.H. Freeman, ISBN 0716710455 A7.1: AN1, pg.249.
 Hardy, G. H.; Wright, E. M. (1980), An Introduction to the Theory of Numbers (Fifth edition), Oxford: Oxford University Press, ISBN 9780198531715
 Ireland, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (Second edition), New York: Springer, ISBN 038797329X
 Lemmermeyer, Franz (2000), Reciprocity Laws: from Euler to Eisenstein, Berlin: Springer, ISBN 3540669574
 Kenneth L. Manders; Leonard Adleman (1978), "NPComplete Decision Problems for Binary Quadratics", Journal of Computer and System Sciences 16 (2): 168–184, doi:10.1016/00220000(78)900442.
External links
Categories: Modular arithmetic
 NPcomplete problems
 Quadratic residue
Wikimedia Foundation. 2010.
См. также в других словарях:
quadratic residue — Math. a number x that is relatively prime to a given integer y and for which a number z exists whose square gives the same remainder as x when divided by y. * * * … Universalium
quadratic residue — Math. a number x that is relatively prime to a given integer y and for which a number z exists whose square gives the same remainder as x when divided by y … Useful english dictionary
Quadratic residue code — A quadratic residue code is a type of cyclic code.There is a quadratic residue code of length pover the finite field GF(l) whenever pand l are primes, p is odd andl is a quadratic residue modulo p.Its generator polynomial as a cyclic code is… … Wikipedia
Quadratic reciprocity — The law of quadratic reciprocity is a theorem from modular arithmetic, a branch of number theory, which shows a remarkable relationship between the solvability of certain quadratic equations modulo different prime moduli.Although it allows us to… … Wikipedia
Quadratic residuosity problem — The quadratic residuosity problem in computational number theory is the question of distinguishing by calculation the quadratic residues in modular arithmetic for a modulus N , where N is a composite number. This is an important consideration in… … Wikipedia
Quadratic equation — This article is about quadratic equations and solutions. For more general information about quadratic functions, see Quadratic function. For more information about quadratic polynomials, see Quadratic polynomial. In mathematics, a quadratic… … Wikipedia
Quadratic — In mathematics, the term quadratic describes something that pertains to squares, to the operation of squaring, to terms of the second degree, or equations or formulas that involve such terms. Quadratus is Latin for square . Mathematics Algebra… … Wikipedia
Quadratic sieve — The quadratic sieve algorithm (QS) is a modern integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is… … Wikipedia
quadratic — 1. adjective a) square shaped b) of a polynomial, involving the second power (square) of a variable but no higher powers, as . 2. noun A quadratic polynomial, function or equation. See Also: quadrate, quadratic equation, quadratic fo … Wiktionary
Quadratic Gauss sum — For the general type of Gauss sums see Gaussian period, Gauss sumIn mathematics, quadratic Gauss sums are certain sums over exponential functions with quadratic argument. They are named after Carl Friedrich Gauss, who studied them… … Wikipedia