1
$\begingroup$

The calculation of the period of the "modulo exponentiation" function: $$ f_a(r) = a^r (mod \ N) $$ is a step of the quantum algorithm for factorizing $N$, where $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$ (or even $N-1$), with a classical calculation, in polynomial time? Here, "period" means the minimum $r$ satisfying the equation $a^r=1 (mod \ N)$.

If the factors are not enough, 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$

1 Answer 1

3
$\begingroup$

The quantity $r$ is known as the order of $a$ in the multiplicative group $\mathbb{Z}^*_N$. The order of the group is $\phi(N)$, which you can compute if you know the factorization of $N$. Next, you need to factor $\phi(N)$, say $\phi(N) = \prod_{i=1}^m p_i^{d_i}$. For each $i$, find the largest $e_i$ such that $a^{\phi(N)/p_i^{e_i}} \equiv 1 \pmod{N}$. The order of $a$ is then $\prod_{i=1}^m p_i^{d_i-e_i}$. This works since $\mathbb{Z}^*_N$ is an Abelian group which decomposes as a direct group of Abelian groups of orders $p_1^{d_1},\ldots,p_m^{d_m}$.

When $N$ is prime, $\phi(N) = N - 1$, and so all you need to know is the factorization of $N - 1$.

$\endgroup$

Your Answer

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

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