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\}$