← •   HOME  • UP  •   →
Top/Tools/Square roots  

16.5. Discrete Square Roots


Discrete square roots

Definition. Say that s is a discrete square root of x (mod m) if s2 ≡ x (mod m).

For example, 5 is a discrete square root of 8 (mod 17) since 25 ≡ 8 (mod 17). −5 is also a discrete square root of 8 (mod 17).

Not every value has a discrete square root. Here are all the squares mod 17.

x x2 mod 17
0 0
1 1
2 4
3 9
4 16
5 8
6 2
7 15
8 13
9 13
10 15
11 2
12 8
13 16
14 9
15 4
16 1

You can see that there is no square root of 3.

A value that has a square root (mod m) is called a quadratic residue (mod m). When the modulus is prime, each quadrative residue other than 0 has two square roots: s and −s.

When the modulus m = pq where p and q are different primes, a quadratic residue that is relatively prime to m has 4 square roots (two contributed by p, two by q). Here is a table of squares mod 15.

x x2 mod 15
0 0
1 1
2 4
3 9
4 1
5 10
6 6
7 4
8 4
9 6
10 10
11 1
12 9
13 4
14 1

The Discrete Square Root Problem

The Discrete Square Root Problem is as follows.

Input. Two integers x and m, where m > 1.

Output. A square root of x (mod m), or an indication that x has no square root mod m.

If you know the prime factors of m, then there is a polynomial-time algorithm to solve the Discrete Square Root Problem.


A randomized reduction from factoring to finding discrete square roots

This section focuses on the problem of finding discrete square roots (mod m) where m = pq and the factorization is not known. We can assume that p and q are large; otherwise, it is easy to solve the Discrete Square Root Problem by factoring m.

Theorem. If there is a polynomial-time algorithm to solve the Discrete Square Root Problem (mod m = pq), then there is a polynomial-time randomized algorithm to factor such numbers m.

Proof. We do a randomized reduction from factoring to computing discrete square roots. Suppose that dsr(x) returns a discrete square root of x (mod m), if one exists.

Assume without loss of generality that 0 < dsr(x) < m.

To factor m, do the following.

  1. Choose a random integer x where 0 < x < m. If x is not relatively prime to m, then report that gcd(x, m) is a factor of m.

  2. Compute y = x2 mod m and s = dsr(y).

  3. We know two square roots of y, namely x and −x. But y has 4 square roots, and the dsr algorithm cannot know which of those 4 we have chosen as x.

    If s ≡ x (mod m) or s ≡ −x (mod m), then we have no new information: start again at step 1.

    But, with probability of 1/2, s is not congruent to x or to −x (mod m). Proceed to the next step.

  4. Without loss of generality, assume that s > x. (If not, just swap them.) Then 0 < s − x < m, so s − x is not divisible by m.

    s + x < 2m. So the only way for s + x to be divisible by m is for s + x = m. But that means that s ≡ −x (mod m), which we have found is not true.

    So we see that neither s + x nor s − x is divisible by m.

  5. (s + x)(s − x) ≡ s2 − x2 (mod m)
    ≡ y − y (mod m)
    ≡ 0 (mod m)

    So (s + x)(s − x) = km = kpq for some k.

    Since neither s + x nor s − x is divisible by m, factors p and q must be separated in product (s + x)(s − x): one of s + x is divisible by p and the other is divisible by q.

    But that means gcd(s + x, m) is either p or q, and we have factored m.


Using discrete square roots in a cipher

Here is another cipher. It has some undesirable properties, but at least it is known that decrypting messages is as difficult as factoring the modulus.

Choose two different large prime numbers p and q and let n = pq. A message x is an integer where 0 < x < n.

The encipher function is

E(x) = x2 mod n

With overwhelming likelihood, x is relatively prime to m. To decipher ciphertext c, you find all four discrete square roots of c (which is efficient if you know p and q).

Only one of those square roots should be sensible.

 

← •   HOME  • UP  •   →
Top/Tools/Square roots