In this exercise, you are to make the result of Theorem 2.17 eective. Suppose that we are given a positive integer n, two elements , Z n, and integers ` and m, such that ` = m and gcd(`,m) = 1. Show how to compute Z n such that = m in time O(len(`)len(m) + (len(`) +len(m))len(n)2).

n E Z with Theorem 2.17. Let n be a positive integer. For each E Zh, and all gcd(1, m) = 1, if 1 E (z;)", then E (Zn)". "e (z;)". Since gcd(1, m) = 1, there exist integers s and t Proof: Suppose - such that Ls + mt = I. We then have We now focus on the squares in Z rather than general powers. An integer a is called a quadratic residue modulo n if gcd(a,n) l and a-b2 (mod n) for some integer b; in this case, we say that b is a square root of a modulo n. In terms of residue classes, a is a quadratic residue modulo n if and only if [al E (Z)2. To avoid some annoying technicalities, from now on, we shall consider only the case where n is odd. n E Z with Theorem 2.17. Let n be a positive integer. For each E Zh, and all gcd(1, m) = 1, if 1 E (z;)", then E (Zn)". "e (z;)". Since gcd(1, m) = 1, there exist integers s and t Proof: Suppose - such that Ls + mt = I. We then have We now focus on the squares in Z rather than general powers. An integer a is called a quadratic residue modulo n if gcd(a,n) l and a-b2 (mod n) for some integer b; in this case, we say that b is a square root of a modulo n. In terms of residue classes, a is a quadratic residue modulo n if and only if [al E (Z)2. To avoid some annoying technicalities, from now on, we shall consider only the case where n is odd