Quadratic Residue

(redirected from Quadratic residuosity)

quadratic residue

[kwä¦drad·ik ′rez·ə·dü]
A residue of order 2.

Quadratic Residue


a concept in number theory. A number a for which the congruence x2a (mod m ) has a solution is called a quadratic residue modulo m; in other words, a is a quadratic residue modulo m if for a certain integer x the number x2a is divisible by m; if this congruence has no solution, then a is called a quadratic nonresidue. For example, if m = 11, then the number 3 is a quadratic residue, since the congruence x2 ≡ 3 (mod 11) has the solutions x − 5 and x = 6, and the number 2 is a nonresidue, since there do not exist any numbers x that satisfy the congruence x2 ≡ 2 (mod 11). Quadratic residues are a particular case of residues of degree n for n = 2. If m is equal to an odd prime p, then among the numbers 1, 2, …, p − 1 there are (p − l)/2 quadratic residues and p − l)/2 quadratic nonresidues. The Legendre symbol (a/p) is introduced in order to study quadratic residues for a prime modulus p. It is defined as follows: if a is relatively prime to p, then we put (a/p ) = 1 when a is a quadratic residue and (a/p) = − 1 when a is a quadratic nonresidue. A fundamental theorem is the law of quadratic reciprocity, which states that if p and q are odd primes, then

This relation was discovered about 1772 by L. Euler, a modern formulation was given by A. Legendre, and a complete proof was first given in 1801 by K. Gauss. A convenient generalization of the Legendre symbol is the Jacobi symbol. There are many generalizations of the law of quadratic reciprocity in the theory of algebraic numbers. The distribution of quadratic residues and of the sums of the values of the Legendre symbol has been studied by I. M. Vinogradov and other mathematicians.


Vinogradov, I. M. Osnovy teorii chisel Moscow, 1972.
References in periodicals archive ?
Ibrahim [6] devises a sender-deniable public-key encryption based on quadratic residuosity of a composite modulus and showed how to device a sender-deniable public-key encryption from any trapdoor permutation.
In this section we first describe the notion of deniability and then we introduce the quadratic residuosity of a composite in some details as it represents the basic primitive of the schemes presented in this paper.
The proposed scheme is based on the quadratic residuosity problem [1, 9, 10], of a composite n, which is a product of two distinct primes