Im trying to understand the proof in "The Discrete Logarithm Modulo a Composite Hides O(n) Bits" by Håstad et al, where he shows that the order of a random element in RSA group is big.

I got the most part but there is one transition that I just cannot see (in Proof of Lemma 1.2):

enter image description here

Any suggestions on how I could approach it?

Edit: F is defined as: enter image description here


1 Answer 1


Write $d$ for the order of an element of $(\mathbb Z/P\mathbb Z)^\times$, we know that $d|P-1$, and that there are at most $d$ elements of order exactly $d$ as they all form roots of the polynomial $t^d-1\pmod p$. Then counting the number of elements of order less than some bound $B$ is less than summing $d$ over the divisors of $P-1$ less than $B$. Taking $B=(P-1)/m^\ell$ shows that $F(P-1)$ is an upper bound for the number of elements of order less that $(P-1)/m^\ell$.

Considering all possible $g$ and $P$, we want to know the proportion of $(g,P)$ pairs for which $\mathrm{ord}(g)<B$. We divide into two cases: either we have a $P$ where the number of $g$ of small order is greater than some bound $C$ (this is bounded by $\mathrm{Pr}(F(P-1)>C$), or the chance of picking a $g$ from a set of size less than or equal to $C$ is bounded by $C/X$. Taking $C=X/m^{\ell'}$ gives the formula stated.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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