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:
“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)
“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)
“Kittering’s brain. What we will he think when he resumes life in that body? Will he thank us for giving him a new lease on life? Or will he object to finding his ego living in that human junk heap?”
—W. Scott Darling. Erle C. Kenton. Dr. Frankenstein (Sir Cedric Hardwicke)
“This house was designed and constructed with the freedom of stroke of a forester’s axe, without other compass and square than Nature uses.”
—Henry David Thoreau (1817–1862)
“The Plains are not forgiving. Anything that is shallow—the easy optimism of a homesteader; the false hope that denies geography, climate, history; the tree whose roots don’t reach ground water—will dry up and blow away.”
—Kathleen Norris (b. 1947)