Next: About this document ...
Homework Assignment 2
Due Wednesday October 9
William Stein
Date: Math 124
HARVARD UNIVERSITY
Fall 2002
Instructions: Please work with others, and
acknowledge who you work with in your write up. Some of these
problems will require a computer; others look like a computer might be
helpful, but in fact it isn't. If you use a computer, please describe
how you use the computer (you are not required to use MAGMA).
- (3 points) What is the largest order of an element
of
? You may assume that
the Mersenne number
is prime.
- (4 points) You and Nikita wish to agree on a secret key using
the Diffie-Hellman protocol. Nikita announces that
and
. Nikita secretely chooses a number
and tells you
that
. You choose the random number
. What is the secret key?
- (5 point) You see Michael and Nikita agree on a secret key using the
Diffie-Hellman key exchange protocol. Michael and Nikita choose
and
. Nikita chooses a random number
and tells
Michael that
, and Michael chooses a random
number
and tells Nikita that
. Crack their
code by brute force: What is the secret key that Nikita and Michael
agree upon? What is
? What is
?
- (9 points)
Let
be any prime.
- Prove that there is a primitive root modulo
.
[Hint: Write down an element of
that looks like it might
have order
, and prove that it does. Recall that if
have orders
, with
, then
has order
.]
- Suppose now that
is odd.
Prove that for any
, there is a primitive root modulo
.
- Why did your proof in part (b) not work when
?
- (8 points)
Prove that there are infinitely many primes of the form
as follows.
Suppose
are all primes of the form
.
Let
Suppose
is a prime divisor of
.
- Show that
for any
and that
is odd.
- Prove that the equation
has a solution
in
.
- Deduce that
.
- Conclude that there are infinitely many primes of
the form
.
- (6 points)
In class I asserted that the Riemann Hypothesis is equivalent
to the assertion that for all
,
- Give numerical evidence for (or against?) this assertion.
(I mean the asserted inequality, not the assertion that the inequality
is equivalent to the Riemann Hypothesis.)
- What goes wrong for
?
Next: About this document ...
William A Stein
2002-10-02