Formulation
Given the specific case of N being the product of distinct odd prime numbers p and q, the structure of the squaring map:
- a → a2 mod N
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.
Read more about this topic: Quadratic Residuosity Problem
Famous quotes containing the word formulation:
“In necessary things, unity; in disputed things, liberty; in all things, charity.”
—Variously Ascribed.
The formulation was used as a motto by the English Nonconformist clergyman Richard Baxter (1615-1691)
“You do not mean by mystery what a Catholic does. You mean an interesting uncertainty: the uncertainty ceasing interest ceases also.... But a Catholic by mystery means an incomprehensible certainty: without certainty, without formulation there is no interest;... the clearer the formulation the greater the interest.”
—Gerard Manley Hopkins (1844–1889)
“Art is an experience, not the formulation of a problem.”
—Lindsay Anderson (b. 1923)