Proof that you can solve the discrete logarithm problem given the period of a certain function.

34 Views Asked by At

Given $q$ a prime number , $a$ a primitive root modulo $q$ and $b=a^x \pmod q$. The discrete logarithm problem is to find $x$ (specifically the smallest positive integer $x$ for which the previous equation is true). In quantum computing this is solved efficiently by finding the period of the function $f(y_1,y_2)=b^{y_1}a^{y_2}$. I haven't found a convincing proof that given this period one can find $x$. I would appreciate if someone could give me or link a thorough proof.

I have seen this answer: Discrete Logarithm Problem as Period finding of a function. However in this proof I don't see why you can just assume that $k=0$.

There is also this answer: https://quantumcomputing.stackexchange.com/questions/15009/how-to-build-an-example-of-shors-algorithm-for-the-discrete-log. However I believe that the inverse of r2 modulo 28 doesn't necessarily exist.