# Diffie-Hellman and the last bit

**Number Theory**Level 5

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!)