<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-06-19T14:43:00.320Z
2011-06-19T14:43:00.320Z
Peter Shor 
<p>In 1975, <a href="http://www.sciencedirect.com/science/article/pii/S0022000076800438" rel="nofollow noreferrer">Miller has shown</a> 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&lt;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$.</p>

<p>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})$?</p>

<p>A presentation of Carl Pomerance on "<a href="http://www.math.dartmouth.edu/~carlp/PDF/ordertalk.pdf" rel="nofollow noreferrer">The multiplicative order mod $n$ on average</a>" 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})$?</p>

<p>(Note: There is a <a href="https://cstheory.stackexchange.com/questions/6704/is-the-integer-factorization-problem-harder-than-rsa-factorization-n-pq">related question</a> on generic factoring vs. RSA factoring)</p>

<cc.complexity-theory><cr.crypto-security><factoring>
Lower bounds on the period in integer factorization?
Martin Schwarz
# Lower bounds on the period in integer factorization?

(Asked by: username_0 on 2011-06-19)

In 1975, [Miller has shown](http://www.sciencedirect.com/science/article/pii/S0022000076800438) 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

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](http://www.math.dartmouth.edu/~carlp/PDF/ordertalk.pdf)" 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](https://cstheory.stackexchange.com/questions/6704/is-the-integer-factorization-problem-harder-than-rsa-factorization-n-pq) on generic factoring vs. RSA factoring)

**Tags:** cc.complexity-theory, cr.crypto-security, factoring


---

## 1 answers

### Answer by username_1 on 2011-06-19. Score: 18 | Accepted answer

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.


---

