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