Quadratic Residue - Complexity of Finding Square Roots

Complexity of Finding Square Roots

That is, given a number a and a modulus n, how hard is it

  1. to tell whether an x solving x2 ≡ a (mod n) exists
  2. assuming one does exist, to calculate it?

An important difference between prime and composite moduli shows up here. Modulo a prime p, a quadratic residue a has 1 + (a|p) roots (i.e. zero if a N p, one if a ≡ 0 (mod p), or two if a R p and gcd(a,p) = 1.)

In general if a composite modulus n is written as a product of powers of distinct primes, and there are n1 roots modulo the first one, n2 mod the second, …, there will be n1n2… roots modulo n.

The theoretical way solutions modulo the prime powers are combined to make solutions modulo n is called the Chinese remainder theorem; it can be implemented with an efficient algorithm.

For example:

Solve x2 ≡ 6 (mod 15).
x2 ≡ 6 (mod 3) has one solution, 0; x2 ≡ 6 (mod 5) has two, 1 and 4.
and there are two solutions modulo 15, namely 6 and 9.
Solve x2 ≡ 4 (mod 15).
x2 ≡ 4 (mod 3) has two solutions, 1 and 2; x2 ≡ 4 (mod 5) has two, 2 and 3.
and there are four solutions modulo 15, namely 2, 7, 8, and 13.

Read more about this topic:  Quadratic Residue

Famous quotes containing the words complexity of, complexity, finding, square and/or roots:

    “In times like ours, where the growing complexity of life leaves us barely the time to read the newspapers, where the map of Europe has endured profound rearrangements and is perhaps on the brink of enduring yet others, where so many threatening and new problems appear everywhere, you will admit it may be demanded of a writer that he be more than a fine wit who makes us forget in idle and byzantine discussions on the merits of pure form ...”
    —Marcel Proust (1871–1922)

    “In times like ours, where the growing complexity of life leaves us barely the time to read the newspapers, where the map of Europe has endured profound rearrangements and is perhaps on the brink of enduring yet others, where so many threatening and new problems appear everywhere, you will admit it may be demanded of a writer that he be more than a fine wit who makes us forget in idle and byzantine discussions on the merits of pure form ...”
    —Marcel Proust (1871–1922)

    “A successful social technique consists perhaps in finding unobjectionable means for individual self-assertion.”
    —Eric Hoffer (1902–1983)

    “A man who is good enough to shed his blood for his country is good enough to be given a square deal afterwards. More than that no man is entitled to, and less than that no man shall have.”
    —Theodore Roosevelt (1858–1919)

    “Though of erect nature, man is far above the plants. For man’s superior part, his head, is turned toward the superior part of the world, and his inferior part is turned toward the inferior world; and therefore he is perfectly disposed as to the general situation of his body. Plants have the superior part turned towards the lower world, since their roots correspond to the mouth, and their inferior parts towards the upper world.”
    —Thomas Aquinas (c. 1225–1274)