Download the .ipynb file for this notebook, and place your solutions where indicated (you can make more cells for each problem), keeping the original problem descriptions. Upload only one file, which contains all your work; it should be named "HW04_lastname_firstname". Please include comments in your code; this can also help you get partial credit if your code doesn't work.
Then upload it to Blackboard under the Assignments tab. See Collaboration Policy in Homework section of course webpage (it's the same as it was for previous homeworks).
Grader for this HW (communicate with him about grading issues): Mu Zhao, mu.zhao@stonybrook.edu
(a) Write a function num_primes_mod(n,a,b) that computes the number of primes $p$ less than $n$ with $p\equiv a \bmod b$. For instance num_primes_mod(10,1,4) is $1$, since $5$ is the only prime less than $10$ that is congruent to $1 \bmod 4$. You can use any builtin functions, including next_prime.
(b) Use your function to compute: num_primes_mod(100,1,4), num_primes_mod(100,3,4), num_primes_mod(10^5,1,4), num_primes_mod(10^5,3,4).
(c) What pattern do you notice in (b)? Make a conjecture based on this pattern.
# Your solution goes here
Write a function my_bin(n) that returns the binary representation, represented as a list of $0$'s and $1$'s, of n. Do not use the builtin function bin, which does essentially the same thing, or any related builtin functions.
HINT: To find the the rightmost bit, look at n%2. Then to find the next bit to the left, subtract off the rightmost bit, divide by 2, and then again test modulo 2. Repeat.
# Your solution goes here
Suppose that Alice and Bob are engaged in key-exchange using the Diffie-Helmann algorithm. Alice uses a secret number $a$, and Bob uses a secret number $b.$ Eve knows neither $a$ nor $b$. Alice and Bob choose the prime $p=503$ and the fixed number $3$ for their exchange; Eve knows both of these pieces of information. Alice then sends Bob $$3^a \verb+ % + 503 = 141$$ and Bob sends Alice $$3^b \verb+ % + 503 = 268.$$ This communication is done over a public channel, so Eve knows both of the above numbers. Both Alice and Bob can then compute the shared secret $3^{ab} \verb+ % + 503$ by exponentiation, using their secret numbers.
You are Eve. Find their shared secret $3^{ab} \verb+ % + 503.$
(This problem demonstrates that Diffie-Helmann can be broken if the prime $p$ is too small.)
# Your solution goes here
(a) Write a function is_sum_squares(n) that returns True if $n$ can be written as $a^2+b^2$, where $a,b$ are integers, and False otherwise. For example is_sum_squares(5) is True since $5=1^2+2^2$, while is_sum_squares(3) is False.
(b) Compute is_sum_squares(7), is_sum_squares(11), is_sum_squares(13), is_sum_squares(17), is_sum_squares(19), is_sum_squares(23).
(c) What is the pattern for is_sum_squares(p) when $p$ is prime. (HINT: look at $p \verb + % + 4$.)
# Your solution goes here