Return to Answer

You should find an algorithm finding the root square of 1 module n.

x^2 = 1 mod n

To do that:

• Factorize n in prime factor. n = p1^e1 * p2^e2 * ... * pk^ek
• Find the root for all prime xi^2 = 1 mod pi^ei. easy, it is 1 and -1 (or pi^ei - 1)
• Then use the Chinese theorem to find the solution for x (x = x1 mod x1^e1, x = ..., x = xk mod pk^ek (xi can take 2 value so you will have k^2 answer)

you just need to take the solution which meet your condition

You should find an algorithm finding the root square of 1 module n.

x^2 = 1 mod n

To do that:

• Factorize n in prime factor. n = p1^e1 * p2^e2 * ... * pk^ek
• Find the root for all prime xi^2 = 1 mod pi^ei. easy, it is 1 and -1 (or pi^ei - 1)
• Then use the Chinese theorem to find the solution for x (x = x1 mod x1^e1, x = ..., x = xk mod pk^ek (xi can take 2 value so you will have k^2 answer)

you just need to take the solution which meet your condition

EDIT:

I made a mistake about the power of prime root square result:

• 1 and -1 are the root square of xi^2 = 1 mod pi^ei but there may be other when e1 != 1
• for example: n= 16 we have x^2 = 1 mod 2^4 where 9 is also a solution too (9*9 = 81 = 1)

You should find an algorithm finding the root square of 1 module n.

x^2 = 1 mod n

To do that:

• Factorize n in prime factor. n = p1^e1 * p2^e2 * ... * pk^ek
• Find the root for all prime xi^2 = 1 mod pi^ei. easy, it is 1 and -1 (or pi - 1)
• Then use the Chinese theorem to find the solution for x (x = x1 mod x1^e1, x = ..., x = xk mod pk^ek (xi can take 2 value so you will have k^2 answer)

you just need to take the solution which meet your condition

You should find an algorithm finding the root square of 1 module n.

x^2 = 1 mod n

To do that:

• Factorize n in prime factor. n = p1^e1 * p2^e2 * ... * pk^ek
• Find the root for all prime xi^2 = 1 mod pi^ei. easy, it is 1 and -1 (or pi^ei - 1)
• Then use the Chinese theorem to find the solution for x (x = x1 mod x1^e1, x = ..., x = xk mod pk^ek (xi can take 2 value so you will have k^2 answer)

you just need to take the solution which meet your condition

You should find an algorithm finding the root square of 1 module n.

x^2 = 1 mod n

To do that:

• Factorize n in prime factor. n = p1^e1 * p2^e2 * ... * pk^ek
• Find the root for all prime ai^2 = 1 mod pi^ei (easy, it is 1 and pi-1)
• Then use the Chinese theorem to find the solution for: a1 mod p1^e1 = a2 mod p2^e2 = ... = ak mod pk^ek (ai can take 2 value so you will have k^2 answer)

you just need to take the solution which meet your condition

You should find an algorithm finding the root square of 1 module n.

x^2 = 1 mod n

To do that:

• Factorize n in prime factor. n = p1^e1 * p2^e2 * ... * pk^ek
• Find the root for all prime xi^2 = 1 mod pi^ei. easy, it is 1 and -1 (or pi - 1)
• Then use the Chinese theorem to find the solution for x (x = x1 mod x1^e1, x = ..., x = xk mod pk^ek (xi can take 2 value so you will have k^2 answer)

you just need to take the solution which meet your condition