1.7 KiB
1.7 KiB
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\}`
- a translation on the input
- the