For this assignment, you will submit a single Python source file a4.py
. You
may include answers to the written problems inside a comment block at the beginning of the
file (e.g., using ''' This is a comment. '''
).
For the written problems #15, you may NOT use a programming language or calculator, and you must show your work. When making a claim in an argument, you should reference the fact you are applying.
For the programming problems #67, your file may not import any modules or employ any external library functions associated with integers and sets (unless the problem statement explicitly permits this). You will be graded on the correctness, concision, and mathematical legibility of your code. You may reuse functions that you defined on previous assignments.
 = 
 
 = 




 = 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 

 ≡ 
 ≡ 
 
 ≡ 
 ≡ 
 
 ≡ 
 
≡ 
 
≡ 
 
 = 
 
 = 
 
 = 
 
 = 

 ≡ 
 
≡ 
 
≡ 
 
 ≡ 
 
≡ 

 ≡ 
 
 ≡ 
 
≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 = 
 
= 
 
= 

 = 
 
 = 

phi_four()
) as a subroutine. The algorithm you implement must represent
a polynomialtime reduction to φfour from the intractable problem you choose.
Note: remember that the four primes must be distinct; your reduction must work for all possible instances of the
intractable problem.
getFactor()
that takes a single integer input and
returns exactly one prime factor of its input.
Implement a Python function that solves φfour efficiently by calling getFactor()
as a subroutine.
roots()
that takes two arguments: an integer y as its first argument, and a list of primes
as its second argument. You may assume that all the primes p are such that p ≡ 3 mod 4. Let P be the product of all the primes
in the list. The function should return a set of all the distinct square roots of y^{2} in Z/PZ.
Your implementation must be efficient (i.e., it may not iterate over all possible values in Z/PZ to look for square roots).