One of the fundamental elements of Shor's algorithm is the calculation of the function: $$ f_a(r) = a^r (mod \ N) $$ where $N$ is the number to be factored and $a$ is a number chosen with some limitation. The quantum circuit is able to find the period of $f(r)$ in time polynomial in the number of bits of $N$. This allows us to calculate the factors of $N$ in polynomial time.

I'm looking for an inverse relation. Is it possible to find the period, from the knowledge of the factors of $N$ and $N-1$, with a classical calculation, in polynomial time? (EDIT: here "period" means the minimum $r$ satisfying the equation.)

If not, I would like to know if there is any other characterization of $N$ that allows us to calculate the period in polynomial time. This latter question is quite vague, since the period itself can be seen as a "characterization" of $N$; to make it more precise, I specify that I'm looking for a "characterization" in the form of a set of numbers $v_i$, depending on $N$ but not on $a$, such that the period of $f_a(r)$ can be calculated in polynomial time from $v_i$ and $a$.

I know that there are several results in number theory connected to this problem, e.g. if $N$ is prime then $r$ divides $N-1$, but I was not able to find a general recipe that always works in polynomial time, nor to show that it is not possible.

  • $\begingroup$ This question is classic, and much more should be asked in another forum $\endgroup$
    – Ron Cohen
    Mar 5 at 18:14
  • $\begingroup$ The comments should be supported by literature references. Can you provide a reference where this question is explicitly answered? I do not think so. The answer must be explicit, it is not enough to cite a generic book on number theory. About the second part of the comment, yes, maybe another forum would be more appropriate, but "quantum computing" is much more responsive than others. Actually, you claim that you know the answer: this means that this forum is not so wrong. $\endgroup$ Mar 6 at 11:43
  • 2
    $\begingroup$ It doesn't answer your question, but maybe you'll find it interesting: this hilarious paper shows that if the factors of $N$ are known it is easy to find $a$ such that the period is equal to 2. $\endgroup$ Mar 7 at 19:42
  • 1
    $\begingroup$ If $N=pq$ then $a^{(p-1)(q-1)} = 1 \mod N$, for $a$ belonging to the multiplicative group modulo $N$. Is this what you want? It gives you a period of the function, albeit not necessarily the minimal one. $\endgroup$ Mar 7 at 19:54
  • $\begingroup$ I edited the question to clarify that I need the minimum. With your method, I get a multiple of the required r, so I still have to make a factorization, while I'm asking for a polynomial time algorithm. Is this correct? The final aim is this: mathoverflow.net/questions/417142/… That problem reduces to this question noticing that we can uniformly sample numbers in the form of their factors. $\endgroup$ Mar 8 at 9:36


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.