Quadratic residuosity problem
Encyclopedia
The quadratic residuosity problem in computational number theory
is the question of distinguishing by calculating the quadratic residues modulo
N, where N is a composite number
. This is an important consideration in contemporary cryptography
.
s p and q, the structure of the squaring map:
on the multiplicative group of invertible residues modulo N
, is as a group homomorphism
with kernel
a Klein group of order four. The image is therefore of size roughly N/4. More precisely, it is of order:
In contrast, the same mapping modulo prime P has the kernel of order 2 and the image of order (P − 1)/2. In this case it is easy to characterize the image computationally, since the Jacobi symbol
takes the value +1 precisely on quadratic residues modulo P.
Modulo composite N the corresponding Jacobi symbol characterizes a subgroup
of the residues which is larger by factor of two; that is, it rules out roughly half of the residues modulo N, while the problem as posed is to characterize a subset of size a quarter of N. This difference constitutes the quadratic residuosity problem, in this particular but essential case of N being the product of two primes.
The computational hardness assumption is that bridging this gap can only to be done by lengthy calculation, when quantified in terms of the size of N.
Computational number theory
In mathematics, computational number theory, also known as algorithmic number theory, is the study of algorithms for performing number theoretic computations...
is the question of distinguishing by calculating the quadratic residues modulo
Modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
N, where N is a composite number
Composite number
A composite number is a positive integer which has a positive divisor other than one or itself. In other words a composite number is any positive integer greater than one that is not a prime number....
. This is an important consideration in contemporary cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
.
Formulation
Given the specific case of N being the product of distinct odd prime numberPrime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
s p and q, the structure of the squaring map:
- a → a2 mod N
on the multiplicative group of invertible residues modulo N
Multiplicative group of integers modulo n
In modular arithmetic the set of congruence classes relatively prime to the modulus n form a group under multiplication called the multiplicative group of integers modulo n. It is also called the group of primitive residue classes modulo n. In the theory of rings, a branch of abstract algebra, it...
, is as a group homomorphism
Group homomorphism
In mathematics, given two groups and , a group homomorphism from to is a function h : G → H such that for all u and v in G it holds that h = h \cdot h...
with kernel
Kernel (algebra)
In the various branches of mathematics that fall under the heading of abstract algebra, the kernel of a homomorphism measures the degree to which the homomorphism fails to be injective. An important special case is the kernel of a matrix, also called the null space.The definition of kernel takes...
a Klein group of order four. The image is therefore of size roughly N/4. More precisely, it is of order:
In contrast, the same mapping modulo prime P has the kernel of order 2 and the image of order (P − 1)/2. In this case it is easy to characterize the image computationally, since the Jacobi symbol
Jacobi symbol
The Jacobi symbol is a generalization of the Legendre symbol. Introduced by Jacobi in 1837, it is of theoretical interest in modular arithmetic and other branches of number theory, but its main use is in computational number theory, especially primality testing and integer factorization; these in...
takes the value +1 precisely on quadratic residues modulo P.
Modulo composite N the corresponding Jacobi symbol characterizes a subgroup
Subgroup
In group theory, given a group G under a binary operation *, a subset H of G is called a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H x H is a group operation on H...
of the residues which is larger by factor of two; that is, it rules out roughly half of the residues modulo N, while the problem as posed is to characterize a subset of size a quarter of N. This difference constitutes the quadratic residuosity problem, in this particular but essential case of N being the product of two primes.
The computational hardness assumption is that bridging this gap can only to be done by lengthy calculation, when quantified in terms of the size of N.