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)

    “One of the many reasons for the bewildering and tragic character of human existence is the fact that social organization is at once necessary and fatal. Men are forever creating such organizations for their own convenience and forever finding themselves the victims of their home-made monsters.”
    —Aldous Huxley (1894–1963)

    “If magistrates had true justice, and if physicians had the true art of healing, they would have no occasion for square caps; the majesty of these sciences would of itself be venerable enough. But having only imaginary knowledge, they must employ those silly tools that strike the imagination with which they have to deal; and thereby, in fact, they inspire respect.”
    —Blaise Pascal (1623–1662)

    “Sensuality often accelerates the growth of love so much that its roots remain weak and are easily pulled up.”
    —Friedrich Nietzsche (1844–1900)