9
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ This question is classic, and much more should be asked in another forum $\endgroup$
    – Ron Cohen
    Mar 5, 2022 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, 2022 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, 2022 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, 2022 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, 2022 at 9:36

2 Answers 2

2
$\begingroup$

I second the comment that this would be a straightforward exercise in an introductory number theory course, and if you're thinking about Shor's algorithm in this way, an introductory number theory course is a good idea anyway.

But here's an explicit answer:

If you know the factors of $\varphi(N)$, you can find the period of an arbitrary element in polynomial time

Suppose $\varphi(N) = p_1^{n_1}\cdot\dots\cdot p_k^{n_k}$ for some prime factors $p_1$ to $p_k$. Let $a$ be any integer modulo $N$. We know the period of $a$ divides $\varphi(N)$, so the perod must have the form $p_1^{a_1}\dots p_k^{a_k}$, where $a_i\leq n_i$ for all $i$. Moreover, we know that $f_a(r)=1$ if and only if the period of $a$ divides $r$.

Let $r = p_1^{r_1}\dots p_k^{r_k}$ for $r_i \leq n_i$. We know that $p_1^{r_1}\dots p_k^{r_k}$ divides $p_1^{a_1}\dots p_k^{a_k}$ if and only if $r_i\leq a_i$ for all $i$. Therefore, $f_a(r)=1$ if and only if $r_i\leq a_i$ for all $i$.

Given this, we start by setting $r=\varphi(N)$, and then from $i=1$ to $k$, we divide $r$ by $p_i$ and check $f_a(r)$. If $f_a(r)=1$, then we know $r_i$ (the power of $p_i$ in $r$) is still at least as large as $a_i$, and if $f_a(r)\neq 1$ we know $r_i < a_i$. Checking this way for all prime factors will reveal all $a_i$, which gives the period.

The above algorithm takes at most $n_1+\dots + n_k$ evaluations of $f_a$. We know that $k$ and all $n_i$ are in $O(\log(N))$, and since $f_a$ is also polynomial in $\log(N)$, the entire process is polynomial in $\log(N)$.

Generally, the factors of $N$ will not be enough

Factoring $N$ does not always give you the factors of $\varphi(N)$. Let $p$ and $q$ be two primes such that $N = 2pq+1$ is prime. We know the factorization of $N$ (just itself), but $\varphi(N) = N- 1= 2pq$ is hard to factor (the factor of 2 is easy to find, but $N/2=pq$ will be hard to factor).

$\endgroup$
2
$\begingroup$

I would have written a comment to extend on Sam's answer, but since I am seemingly not able to do this since I seldom use this forum, I will write a follow-up answer here instead:

  • If you wish to sample $a$ uniformly at random from $\mathbb Z_N^*$, compute the order $r$ of $a$, and then return $r$ without explicitly returning $a$, then you can in fact do this knowing only the factorization of $N$.

    This is useful in the context of the post-processing algorithm in [E21b], that factors $N$ completely into all of its prime factors with very high success probability given $r$.

  • If you actually need both $a$ and $r$ to be explicitly returned (e.g. because you want to test Shor's original post-processing algorithm that splits $N$ with probability at least $1/2$), then you can simulate order finding heuristically by factoring out all small divisors of all $p_i - 1$ for $N = p_1^{e_1} \cdot \ldots \cdot p_n^{e_n}$.

Both of these simulation methods are explained and implemented in the factoritall GitHub repository, alongside the post-processing algorithm from [E21b].

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.