# Discrete Logarithm

- given a prime multiplicative [[group]] s.t. $`g^x`$ is modular exponentiation, the "discrete log problem" is solving for $`\log_g g^x`$ given $`g`$ and $`g^x`$
- classically hard: requires $`p`$ guess-and-checks, which is infeasible for $`p \gtrsim 2^{256}`$
- [[quantum-computing]]
  - the $`g^t`$ of an element of a prime multiplicative group is periodic with respect to $`t`$
  - so given generator $`g`$ and element $`a`$, we want to find $`t`$ s.t. $`g^t = a`$
  - we define a function $`f : \mathbb{Z}_{p-1} \times \mathbb{Z}_{p-1} \to \mathbb{Z}_p^*`$
  - $`f\left(x,y\right) = g^{x} a^{-y}`$
  - finding the period of this function tells us $`t`$
    - $`f\left(0,0\right) = 1`$
    - $`f\left(t,1\right) = 1`$
    - $`f\left(\left(p-1\right)t,p-1\right) = 1`$
  - we can use the [[quantum-fourier-transform]] to discover the period of a function
    - a translation on the input $`f\left(x, y + s\right)`$ corresponds to a phase change on the output $` = g^{-s}`$
    - this means $`f\left(x,y\right) = f\left(x - x', y - y'\right) \Leftrightarrow \left(x - x', y - y'\right) \in H`$
    - where $`H = \left\{\left(0, 0\right), \left(t, 1\right), \ldots\right\}`$
    - measure the "output" state (rightmost state) of $`\mathcal{U}_f\left(\mathbb{F}_{p-1} \otimes \mathbb{F}_{p-1} \otimes \mathbf{1}\right)\left(\ket{0,0}\ket{0}\right)`$ and throw it away
    - the result will be $`\ket{H + \left(0,s\right)} = \left(\mathbf{1} \otimes \mathsf{T}^s\right)\ket{H}`$ for some unknown shift $`s`$
    - we can do another QFT to get $`\left(\mathbf{1} \otimes \mathsf{S}^s\right)\left(\mathbb{F}_{p-1} \otimes \mathbb{F}_{p-1}\right)\ket{H}`$
    - $`H^\bot = \left\{\left(0,0\right),\left(1,-t\right),\ldots\right\}`$