Calculate the period (like in Shor's algorithm) from the factors?

Question

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.

Answer 1

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).

Answer 2

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].