# Diffie-Hellman and the last bit

Let $p = 10007$ and $g=5.$ You may assume that $p$ is prime and $g$ is a primitive root mod $p.$

Suppose Alice and Bob are carrying out the Diffie-Hellman protocol with these parameters. As a first step, Alice sends Bob $g^m \pmod p$ and Bob sends Alice $g^n \pmod p,$ where $m$ and $n$ are secret positive integers less than $p,$ known only to Alice and Bob, respectively.

An eavesdropper Eve knows the values of $p$ and $g$, and sees the transmissions. In particular, she sees that Alice sends Bob the number $2$ and Bob sends Alice the number $3.$ What can Eve deduce about $m$ and $n$ quickly? (That is, much more quickly than computing $m$ and $n$--please don't compute $m$ and $n$ to solve the problem!)

×