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:
“It is not only their own need to mother that takes some women by surprise; there is also the shock of discovering the complexity of alternative child-care arrangements that have been made to sound so simple. Those for whom the intended solution is equal parenting have found that some parents are more equal than others.”
—Elaine Heffner (20th century)
“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)
“I walked by the Union Square Bar, I was gonna go in. And I saw myself, my reflection in the window. And I thought, “I wonder who that bum is.” And then I saw it was me. Now look at me, I’m a bum. Look at me. Look at you. You’re a bum.”
—J.P. (James Pinckney)
“Sprung from the West,
He drank the valorous youth of a new world.
The strength of virgin forests braced his mind,
The hush of spacious prairies stilled his soul.
His words were oaks in acorns; and his thoughts
Were roots that firmly gript the granite truth.”
—Edwin Markham (1852–1940)