Order of random element in RSA is big

Question

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):

Any suggestions on how I could approach it?

Edit: F is defined as:

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.