Time complexity of classical period finding

Question

Shor's algorithm for a quantum computer uses period finding in the quantum part to factor a number. For example, finding $r$ in $1 = a^r \; (mod \; N)$ will allow you to find two factors of a number $N$.

There also exists a step by step algorithm to calculate this period $r$ classically, which I found here.

1. Pick a random number $$ ($ < $). Check that coprime with $$.
2. Find smallest $r$, for which a $a^r ≡ 1 \; (mod \; N)$ (i.e., $r$ is the order of $a$).
3. If $r$ is odd, choose another $a$ and repeat (go back to Step 1). Probability of going back is ∼50%.
4. If $r$ is even, then $a^{\frac{r}{2} − 1} a^{\frac{r}{2} + 1} ≡ 0 \; (mod \; )$. If $a^{\frac{r}{2} + 1} ≡ 0\; (mod \; N)$, choose another and repeat (go back to Step 1; this is very rare).
5. Since $N$ = and & are primes, then $a^{\frac{r}{2} - 1}$ is a multiple of , and $a^{\frac{r}{2} + 1}$ is a multiple of (or vice versa). Find the greatest common divisor (GCD) of and $a^{\frac{r}{2} ± 1}$, they will be and .

Is there a time complexity for step 2 (classically)? Or specifically the period finding algorithm?

PS: I am not asking about prime factorization in general, just period finding.

Thanks!

Answer 1

In general I don't think we know any period finding algorithms that are faster than linear in the period size. You can look here for some algorithms that are in that area which are memory efficient.

But, if you have a sequence $a_l$ where you are able to compute $a_l$ for large $l$ efficiently, then you can use the Baby-step giant-step algorithm to find (a multiple of) the period of $a_l$. This is the case in your algorithm, since we can compute $a^l \bmod n$ in $\mathcal{O}(\log(l))$ operations mod $n$.
This leads to an $\mathcal{O}(\sqrt{n})$ algorithm to complete step 2 (omitting factors $\log(n)$).

However, if you know on top of that, that the period is smooth, then you can do the following.
As an example, we can use your sequence that we find in step 2 again:
Note that $r \mid (p-1)(q-1)$. Assume that $p-1$ and $q-1$ are both $k$-smooth, where $k$ is not too big. Define \begin{equation} m = \prod_{r \text{ prime}}^{k} r^{\lfloor{\log_r{n}\rfloor }}. \end{equation} Then you can check that $a^m = 1 \bmod n$. By throwing away factors $r$ you can also obtain the exact period this way.
In practice we usually don't know beforehand if $(p-1)(q-1)$ is smooth or not. Therefore we try an $m$ as defined above and look if $a^m = 1 \bmod n$.
Since $m$ is of size $\mathcal{O}(n^k)$, this algorithm has complexity $\mathcal{O}(k\log(n))$ operations mod $n$. This is basically the idea behind Pollard's $p − 1$ algorithm.
If $k$ is not too big, then this method is efficient, but in general it is not.