Question

In this problem you will implement an algorithm for computing all the square roots of a congruence class in ℤ/nℤ, given a complete factorization of n into its distinct prime factor powers (assuming all the prime factors are in 3 + 4ℤ).

a) Implement a Python function sqrtsPrime(a, p) that takes two arguments: an integer a and a prime number p. You may assume that a and p are coprime. If p is not in 3 + 4ℤ or a has no square roots in ℤ/pℤ, the function should return None. Otherwise, it should return the two congruence classes in ℤ/pℤ that solve the following equation:

x² ≡ a (mod p)

>>> sqrtsPrime(2, 7)

(3, 4)

>>> sqrtsPrime(5, 7) # 5 has no square roots

None

>>> sqrtsPrime(5, 17) # 17 mod 4 =/= 3

None

>>> sqrtsPrime(763472161, 5754853343)

(27631, 5754825712)

b) Implement a Python function sqrtsPrimePower(a, p, k) that takes three arguments: an integer a, a prime number p, and a positive integer k. You may assume that a and p are coprime. If p is not in 3 + 4ℤ or a has no square roots in ℤ/pkℤ, the function should return None. Otherwise, it should return the congruence classes in ℤ/pkℤ that solve the following equation:

x² ≡ a (mod p² )

>>> sqrtsPrimePower(2, 7, 2)

(10, 39)

>>> sqrtsPrimePower(763472161, 5754853343, 4)

(27631, 1096824245608362247285266960246506343570)

c) Implement a Python function equation: x2 ≡ a (mod n) sqrts(a, pks) that takes two arguments: an integer a and a list of tuples pks in which each tuple is a distinct positive prime number paired with a positive integer power. You may assume that a and n are coprime. You may assume that all the primes in pks are in 3 + ℤ/4ℤ (if any are not, the function should return None). Let n be the product of all the prime powers in the list pks. Then the function should return a set of all the distinct square roots of a in ℤ/nℤ that are solutions to the following equation:

x² ≡ a (mod n)

Here is a helpedr function

def combinations(ls):

if len(ls) == 0:

return [[]]

else:

return [ [x]+l for x in ls[0] for l in combinations(ls[1:]) ]

Answer 1

'''

def sqrtsPrime(a,p):
   if (pow(p,1,4)==3):
w = floo
r((p+1)/4)
       q = pow(a,w,p)
       test = a * (w % p)
       thing1 = pow(q,2,p)
       ex1 = (2 % p)
       thing2 = pow(a,1,p)
       if ( thing1 == thing2):
           return (q,-q%p)
   return None

'''
def sqrtsPrimePower(a, p, k):
   if p%4 != 3:
       return None
   x = pow(a,((p + 1)//4), p)
   c = (inv(x, p) * inv(2, p) * ((a - pow(x,2))//pow(p,1)))%p
   y = (x + (c * pow(p,1)))
   #if not (pow(y,2,pow(p,k)) == a):
   #   return None
   return (y, pow(-y,1,pow(p,k)))
'''  
def sqrtsPrimePower(a, p, k):
   if (pow(p,1,4)==3):
       if (k > 1):
           (x1, x2) = sqrtsPrimePower(a, p, k-1)
       else:
           (x1, x2) = sqrtsPrime(a, p)
       if (x1>x2):
           (x1,x2) = (x2,x1)
       r = floor((a - pow(x1,2))/pow(p, k-1))
       c = pow(((inv(x1, p))*(inv(2, p))*r), 1, p)
       som = pow(p,k)
       lemma = x1 + c * pow(p, k-1)
       con = pow(lemma, 1, som)
       if (pow(con,2,som) == pow(a, 1, som)):
           return (con, pow(-con, 1, som))
return None