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)
“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)
“As a father I had some trouble finding the words to separate the person from the deed. Usually, when one of my sons broke the rules or a window, I was too angry to speak calmly and objectively. My own solution was to express my feelings, but in an exaggerated, humorous way: “You do that again and you will be grounded so long they will call you Rip Van Winkle II,” or “If I hear that word again, I’m going to braid your tongue.””
—David Elkind (20th century)
“Mark you the floore? that square & speckled stone,
Which looks so firm and strong,
Is Patience:”
—George Herbert (1593–1633)
“Now fades the lasts long streak of snow,
Now burgeons every maze of quick
About the flowering squares, and thick
By ashen roots the violets blow.”
—Alfred Tennyson (1809–1892)