Lower bounds on the period in integer factorization?

Question

In 1975, Miller has shown how to reduce the factorization of integer $N$ to finding the period $r$ of a function $f(x)=a^x\;\bmod\;N$ such that $f(x+r)=f(x)$ with some randomly chosen $a<N$. It is well known that Shor's algorithm can find $r$ efficiently on a quantum computer, whereas it is believed to be intractable for a classical computer to find $r$.

My question now is: Are there any known lower bounds on $r$ for random $N$? Are there any bounds on $r$ given $N=pq$ is chosen as in RSA? Clearly, $r$ must be $\Omega(\log(N))$ as otherwise one could just evaluate $f(x)$ on $O(\log(N))$ successive points to figure out $r$ classically. Would it suffice to break RSA if there was a classical factoring algorithm which only works under some assumption on the distribution of $r$, e.g. $r \in \Theta(N/\log(N))$ or $r \in \Theta(\sqrt{N})$?

A presentation of Carl Pomerance on "The multiplicative order mod $n$ on average" cites evidence that $r$ is $O(N/\log(N))$ on average over all $N$, yet I'm not sure whether a classical algorithm which can factor $N$ under the hypothesis of $r \in O(N/\log(N))$ would conclusively break RSA. Can $N$ be adverserially chosen to have $r \in O(N))$ or $r \in O(\sqrt{N})$?

(Note: There is a related question on generic factoring vs. RSA factoring)

Answer 1

If $N=pq$, the period $r$ will always be a divisor of $\phi(N)=\mathrm{lcm}(p-1,q-1)$. If you choose $p-1=2p'$ and $q-1=2q'$ for $p',q'$ prime, then unless you are incredibly lucky, we will have $r \geq p'q' \approx N/4$. I also believe that we can efficiently find primes $p$ with $p=2p'+1$ by choosing candidates randomly and testing them (this is true if the events that $p$ and $p'$ are prime are roughly independent; I don't know whether this has been proven). Thus, by carefully choosing your primes, RSA will still be secure against attacks even with the additional hypothesis about easy factoring.

I suspect random numbers $N$ or random $N=pq$ are extremely unlikely to have $r \in O(\sqrt{N})$, but I don't have a proof of this offhand. The hypothesis $r\in O(\sqrt{N})$ is extremely strong, and I wouldn't be surprised if an efficient factoring algorithm were already known for this case.