Quadratic residuosity problem

Let $n$ be an odd composite positive integer whose prime factors are not known. Let $a$ be in integer that is relatively prime to $n$ . How hard is it to determine whether $a$ is a square modulo $n$ ? That is, how hard is it to know whether the congruence equation $x^2 \equiv a \ \text{mod} \ n$ has solutions in $x$ ? Here is a more precise formulation of the problem called quadratic residuosity problem.

Quadratic Residuosity Problem
Let $N=p \times q$ where $p$ and $q$ are two distinct odd primes. The values of $p$ and $q$ are not known but the value of $N$ is known. Let $a$ be an integer that is relatively prime to $N$ such that the Jacobi symbol $(\frac{a}{N})=1$ . Determine whether $a$ is a quadratic residue modulo $N$ , i.e., whether $a$ is a square modulo $N$ .

When the modulus $N$ is relatively small, we can simply square the numbers that are relatively prime to $N$ until we reach a value that is the same as $a$ . When $N$ is large (or when $p$ and $q$ are large), the quadratic residuosity problem is believed to be computationally difficult. The intractability of the problem has implications in cryptography. For example, the security of the Goldwasser-Micali cryptosystem is based on the difficulty of the quadratic residuosity problem. See here for a discussion of the Goldwasser-Micali cryptosystem.

More on the Problem

When the modulus is a prime $p$ , there is an efficient algorithm to determine whether $a$ is a square modulo $p$ or whether $a$ is a quadratic residue modulo $p$ . One way is the use Euler’s criterion by evaluating $a^{\frac{p-1}{2}}$ modulo $p$ . We can also evaluate the Legendre symbol $(\frac{a}{p})$ . Both results are the same value. If the result is congruent to 1, then $a$ is a quadratic residue modulo $p$ . If the result is congruent to -1, then $a$ is a quadratic nonresidue modulo $p$ .

When $N=p \times q$ as discussed above, the number $a$ is a quadratic residue modulo $N$ if and only if $a$ is a quadratic residue modulo both $p$ and $q$ . If $p$ and $q$ are known, we can evaluate the Legendre symbols $(\frac{a}{p})$ and $(\frac{a}{q})$ . If both are 1, then $a$ is a quadratic residue modulo $N$ . If one or both symbols is a -1, then $a$ is a quadratic nonresidue modulo $N$ . With $p$ and $q$ not known, this is not a feasible approach.

The same tools that work for prime modulus would not work for the composite modulus $N$ . Euler’s criterion is no longer applicable, which is applicable only when the modulus is an odd prime. We can evaluate the Jacobi symbol $(\frac{a}{N})$ by using the law of quadratic reciprocity for the Jacobi symbol. However, the value of the Jacobi symbol $(\frac{a}{N})$ may not nicely correspond to quadratic residue or quadratic nonresidue, unlike the situation for the Legendre symbol. For the Legendre symbol, $(\frac{a}{p})=1$ means $a$ is a quadratic residue modulo the odd prime $p$ and $(\frac{a}{p})=-1$ means $a$ is a quadratic nonresidue modulo $p$ . When the Jacobi symbol $(\frac{a}{N})$ has the value of -1, we can conclude that $a$ is a quadratic nonresidue modulo $N$ . But when $(\frac{a}{N})$ is 1, we cannot conclude that $a$ is a quadratic residue modulo $N$ . When $(\frac{a}{N})=1$ , sometimes $a$ is a quadratic residue (when $a$ is a quadratic residue modulo both $p$ and $q$ ) and sometimes $a$ is a quadratic nonresidue (when $a$ is a quadratic nonresidue modulo both $p$ and $q$ ). The examples in the next section illustrate that the Jacobi symbol may not give reliable information.

Examples

Evaluate the following Jacobi symbols $(\frac{26807757}{80549389})$ and $(\frac{1370266}{80549389})$ .

See here for information on Jacobi symbol. In the following derivation, we do not factor any odd number and instead use the law of quadratic reciprocity to flip the symbols. Once the top value is greater than the bottom value, we reduce the top value modulo the bottom value. Whenever the top value is even, we factor out the 2.

$\displaystyle \begin{aligned} \biggl(\frac{26807757}{80549389}\biggr)&=\biggl(\frac{80549389}{26807757}\biggr) =\biggl(\frac{126118}{26807757}\biggr) \\&=\biggl(\frac{2}{26807757}\biggr) \times \biggl(\frac{63059}{26807757}\biggr) \\&=(-1) \biggl(\frac{26807757}{63059}\biggr) =-\biggl(\frac{7682}{63059}\biggr) \\&=-\biggl(\frac{2}{63059}\biggr) \times \biggl(\frac{3841}{63059}\biggr) \\&=- (-1) \biggl(\frac{63059}{3841}\biggr) =\biggl(\frac{1603}{3841}\biggr) \\&=\biggl(\frac{3841}{1603}\biggr) =\biggl(\frac{635}{1603}\biggr) \\&=-\biggl(\frac{1603}{635}\biggr)=-\biggl(\frac{333}{635}\biggr) \\&=-\biggl(\frac{635}{333}\biggr)=-\biggl(\frac{302}{333}\biggr) \\&=-\biggl(\frac{2}{333}\biggr) \times \biggl(\frac{151}{333}\biggr)\\&=-(-1) \biggl(\frac{333}{151}\biggr)=\biggl(\frac{182}{151}\biggr) \\& =\biggl(\frac{2}{151}\biggr) \times \biggl(\frac{91}{151}\biggr)\\&=- \biggl(\frac{151}{91}\biggr)=- \biggl(\frac{60}{91}\biggr)\\&=- \biggl(\frac{2}{91}\biggr)^2 \times \biggl(\frac{15}{91}\biggr)\\&=- \biggl(\frac{15}{91}\biggr)\\&=- (-1)\biggl(\frac{91}{15}\biggr) =\biggl(\frac{1}{15}\biggr) \\&=1 \end{aligned}$

Following the similar process, we evaluate the second Jacobi symbol as follows.

$\displaystyle \begin{aligned} \biggl(\frac{1370266}{80549389}\biggr)&=\biggl(\frac{2}{80549389}\biggr) \times \biggl(\frac{685133}{80549389}\biggr) \\&=(-1) \biggl(\frac{80549389}{685133}\biggr) =- \biggl(\frac{388828}{685133}\biggr)\\&=- \biggl(\frac{2}{685133}\biggr)^2 \times \biggl(\frac{97207}{685133}\biggr) \\&=- \biggl(\frac{685133}{97207}\biggr)=-\biggl(\frac{4684}{97207}\biggr) \\&=- \biggl(\frac{2}{97207}\biggr)^2 \times \biggl(\frac{1171}{97207}\biggr) \\&=- (1) (-1) \biggl(\frac{97207}{1171}\biggr)=\biggl(\frac{14}{1171}\biggr) \\&=\biggl(\frac{2}{1171}\biggr) \times \biggl(\frac{7}{1171}\biggr) \\&= (-1) (-1) \biggl(\frac{1171}{7}\biggr)=\biggl(\frac{2}{7}\biggr) \\&=1 \end{aligned}$

The values of both Jacobi symbols are 1. The first one corresponds to a quadratic nonresidue modulo $N$ where $N$ = 80,549,389. The second one corresponds to a quadratic nonresidue modulo $N$ . The first Jacobi system corresponds to the equation $x^2 \equiv 26807757 \ \text{mod} \ N$ , which has no solutions. The second symbol corresponds to the equation $x^2 \equiv 1370266 \ \text{mod} \ N$ , which has solutions. One solution is $x \equiv 70254916$ .

These examples illustrate the point that evaluating Jacobi symbols is not a reliable way to solve the quadratic residuosity problem.

$\text{ }$

Dan Ma quadratic residuosity problem

Dan Ma Goldwasser-Micali cryptosystem

Daniel Ma quadratic residuosity problem

Daniel Ma Goldwasser-Micali cryptosystem

Mathematical Cryptography

focusing on the math in public key cryptography

Quadratic residuosity problem

Leave a comment Cancel reply

Share this:

Related

Leave a comment Cancel reply