Lower bounds on the period in integer factorization?
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&#39;$ and $q-1=2q&#39;$ for $p&#39;,q&#39;$ prime, then unless you are incredibly lucky, we will have $r \geq p&#39;q&#39; \approx N/4$. I also believe that we can efficiently find primes $p$ with $p=2p&#39;+1$ by choosing candidates randomly and testing them (this is true if the events that $p$ and $p&#39;$ 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.