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_firstname_lastname". 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).
(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
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) A twin prime is a prime $p$ such that $p+2$ is also prime. Write a function num_twin_primes(n) that computes the number of twin primes less than $n$. For example num_twin_primes(10) is $2$ since $3,5$ are the twin primes less than $10$. You can use builtin functions such as next_prime and is_prime.
(b) Compute num_twin_primes(10^2), num_twin_primes(10^4), num_twin_primes(10^5).
(c) Based on your experiments, make a guess about the behavior of the ratio num_twin_primes(n)/n as $n\to\infty$.
# 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