Complexity of Finding Square Roots
That is, given a number a and a modulus n, how hard is it
- to tell whether an x solving x2 ≡ a (mod n) exists
- 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:
“The price we pay for the complexity of life is too high. When you think of all the effort you have to put in—telephonic, technological and relational—to alter even the slightest bit of behaviour in this strange world we call social life, you are left pining for the straightforwardness of primitive peoples and their physical work.”
—Jean Baudrillard (b. 1929)
“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)
“He, who, in view of its inconsistencies, says of human nature the same that, in view of its contrasts, is said of the divine nature, that it is past finding out, thereby evinces a better appreciation of it than he who, by always representing it in a clear light, leaves it to be inferred that he clearly knows all about it.”
—Herman Melville (1819–1891)
“I would say it was the coffin of a midget
Or a square baby
Were there not such a din in it.”
—Sylvia Plath (1932–1963)
“To the young mind, every thing is individual, stands by itself. By and by, it finds how to join two things, and see in them one nature; then three, then three thousand; and so, tyrannized over by its own unifying instinct, it goes on tying things together, diminishing anomalies, discovering roots running underground, whereby contrary and remote things cohere, and flower out from one stem.”
—Ralph Waldo Emerson (1803–1882)