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)
“Disillusionment in living is finding that no one can really ever be agreeing with you completely in anything.”
—Gertrude Stein (1874–1946)
“Mark you the floore? that square & speckled stone,
Which looks so firm and strong,
Is Patience:”
—George Herbert (1593–1633)
“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)