Proof
As \({\mathbb {Z}}_N^*\) is isomorphic to \({\mathbb {Z}}_{p-1}^+ \times {\mathbb {Z}}_{q-1}^+\) the order \(r \le \phi (N) / \gcd (p-1, q-1)\) where \(\phi (N) = (p-1)(q-1)\). The order r is hence always reduced by a factor \(\gcd (p-1, q-1)\) compared to \(\phi (N)\) due to shared factors. It may be further reduced: This depends on g, and on how \(p-1\) and \(q-1\) factor. To understand the distribution of r, we therefore first seek an expression for the probability of a factor z dividing \(p-1\), and \(q-1\), respectively.
To this end, we use Siegel–Walfisz’ theorem [
18,
19]. In essence it states that as
\(x \rightarrow \infty \) the probability over all primes
\(p \le x\) that
\(p \equiv a \,\, (\text {mod } z)\) is
\(1/\phi (z)\), for
\(z \in [2, \ln ^c(x)]\) a fixed integer, where
c is an arbitrary positive constant, and
a a fixed residue coprime to
z. For
\(a = 1\) this implies that
\(p - 1 \equiv 0 \,\, (\text {mod } z)\), i.e.
z divides
\(p-1\), with probability
\(1/\phi (z)\). The same holds for
\(q-1\). Furthermore, as
\(\phi (z_1 z_2) = \phi (z_1) \cdot \phi (z_2)\) for
\(z_1, z_2\) coprime factors, we may independently analyze the reductions caused by distinct prime powers.
To obtain the lower bound \(P_N(\tau )\) on the probability of \(r \ge \phi (N) / 2^\tau \), we let \({\mathcal {F}}\) be the set of all primes less than \(2^\tau \), and \({\mathcal {F}}'\) the set of all primes greater than \(2^\tau \), and proceed as follows:
In Part 1 of the proof, we compute all reductions \(\phi (N)/r \le 2^\tau \) to which combinations of powers of factors in \({\mathcal {F}}\) give rise, and sum up the associated probabilities, to obtain the probability \(\rho _N(\tau )\). In Part 2, we upper-bound the probability of factors in \({\mathcal {F}}'\) giving rise to a reduction in the order greater than \(2^\tau \), and subtract it from \(\rho _N(\tau )\) to obtain \(P_N(\tau )\).
Part 1 For each
\(f \in {\mathcal {F}}\), let
n be the greatest power of
f such that
\(f^n \le 2^\tau \). As
\(f^e\) divides
\(p-1\), or equivalently
\(q-1\), with probability
\(1/\phi (f^e)\), we have that
$$\begin{aligned} {\Lambda }(e, f) = \left\{ \begin{array}{l@{\quad }l} 1 - 1/(f-1) &{} e = 0 \\ (1-1/f)/((f-1) \, f^{e-1}) &{} e \in [1, n] \\ 1/((f-1) \, f^{n}) &{} e = n + 1 \end{array} \right. \end{aligned}$$
is the probability that
\(f^e\) is the greatest power of
f to divide
\(p-1\), or equivalently
\(q-1\), for
\(e \in [0, n]\), and the probability that
\(f^{n+1}\) divides
\(p-1\), or equivalently
\(q-1\), when
\(e = n + 1\).
For pairwise combinations of \(e_p, e_q \in [0, n+1]\), the probability is \({\Lambda }(e_p, f) \cdot {\Lambda }(e_q, f)\) that \(f^{e_p}\) and \(f^{e_q}\) divide \(p-1\) and \(q-1\), respectively, in the special manner described above.
In the formulation of this lemma, we pick g uniformly at random from \({\mathbb {Z}}_{N}^*\), and consider the order of g. This is equivalent to selecting \(g_p\) and \(g_q\) uniformly at random from the cyclic groups \({\mathbb {Z}}_{p-1}^+\) and \({\mathbb {Z}}_{q-1}^+\), respectively, and considering the order of \((g_p, g_q) \in \mathbb Z_{p-1}^+ \times {\mathbb {Z}}_{q-1}^+ \simeq {\mathbb {Z}}_N^*\).
The probability of selecting
\(g_p\) such that
\(f^{u_p}\) is the greatest power of
f to divide
\(g_p\) for
\(u_p \in [0, e_p)\), leading to a reduction in the order of
\(g_p\) by a factor
\(f^{u_p}\), or such that
\(f^{u_p}\) divides
\(g_p\) for
\(u_p = e_p\), leading to a reduction in the order of
\(g_p\) by a factor
\(f^{u_p}\) when
\(e_p \le n\), or by at least a factor
\(f^{u_p}\) when
\(e_p = n + 1\), is
\({\Pi }(u_p, e_p, f)\), where
$$\begin{aligned} {\Pi }(u, e, f) = \left\{ \begin{array}{ll} (1 - 1/f) / f^{u} &{} \quad u \in [0, e) \quad \text {and} \; e > 0, \\ 1 / f^{e} &{} \quad u = e. \end{array} \right. \end{aligned}$$
Analogously, the probability of selecting
\(g_q\) that is divisible by
\(f^{u_q}\) in the above special manner for
\(u_q \in [0, e_q]\), leading to corresponding reductions in the order of
\(g_q\), is
\({\Pi }(u_q, e_q, f)\).
For the \(g_p\) and \(g_q\) selected, the order of \((g_p, g_q)\) is hence reduced by a factor \(f^{u_p + u_q + u_{pq}}\) for \(e_p, e_q \in [0, n]\) due to \(f \in {\mathcal {F}}\), where \(u_{pq} = \min (e_p - u_p, e_q - u_q)\). The additional reduction by \(f^{u_{pq}}\) is due to shared factors in the orders of \(g_p\) and \(g_q\). If \(e_p = n+1\) and/or \(e_q = n+1\), the reduction is at least \(f^{u_p + u_q + u_{pq}}\); it may be greater, but only if \(f^{u_p + u_q + u_{pq}} > 2^{\tau }\), and all such cases may be treated jointly. Hence, we may model the order \(\phi (N)\) as being reduced by a factor \(f^{u_p + u_q + u_{pq}}\) due to \(f \in {\mathcal {F}}\) with probability \({\Lambda }(e_p, f) \cdot {\Pi }(u_p, e_p, f) \cdot {\Lambda }(e_q, f) \cdot {\Pi }(u_q, e_q, f)\).
Given this analysis, the probability \(\rho _N(\tau )\) that a factor at most \(2^\tau \) is lost due to prime factors in \({\mathcal {F}}\) can be evaluated numerically by computer: Exhaust all products of reductions that combinations of factors in \({\mathcal {F}}\) can give rise to, with the restriction that the product must not exceed \(2^\tau \), and sum up the probabilities associated with each reduction, to obtain \(\rho _N(\tau )\).
Part 2 For factors \(f \in {\mathcal {F}}'\), we upper-bound the probability of the order \(\phi (N)\) being reduced by at least a factor \(f > 2^\tau \) as follows: Let P(f) denote the probability that a factor f divides \(p-1\), and analogously \(q-1\). If f divides both \(p-1\) and \(q-1\), the order is reduced by at least a factor \(f > 2^\tau \). The total probability of this event is \(P(f)^2\). If f divides \(p-1\) but not \(q-1\), or vice versa, the order is reduced by a factor \(f > 2^\tau \) with probability 1/f. The total probability of this event is \(P(f) (1 - P(f)) (1/f) \le P(f)/f\).
To summarize, the probability of reducing the order
\(\phi (N)\) by more than
\(2^\tau \) via
\(f \in {\mathcal {F}}'\), when
\(f \le \ln ^c(x)\) so that
\(P(f) = 1/\phi (f)\) by Siegel–Walfisz’ theorem, is upper-bounded by
$$\begin{aligned} \sum _{f \in {\mathcal {F}}'} \left( \frac{1}{\phi (f)^2} + \frac{2}{f \phi (f)} \right) \le \sum _{f \in {\mathcal {F}}'} \frac{3}{(f-1)^2} \le \sum _{z= 2^\tau + 1}^{\infty } \frac{3}{(z-1)^2} \le \int _{2^\tau }^{\infty } \frac{3}{(z-1)^2} \; \mathrm {d}z = \frac{3}{2^\tau - 1}. \end{aligned}$$
To handle the contribution from factors
\(f > \ln ^c(x)\), we may instead use that
\(P(f) \le \ln (x)/f\) by Claim
2, to obtain the upper bound
$$\begin{aligned} \sum _{f} \left( \frac{\ln ^2(x)}{f^2} + \frac{2 \ln (x)}{f^2} \right) \le \int _{\ln ^c(x) - 1}^{\infty } \frac{3 \ln ^2(x)}{z^2} \;\mathrm {d}z = \frac{3 \ln ^2(x)}{\ln ^c(x)-1} \end{aligned}$$
which, for any
\(c > 2\), may be seen to tend to zero in the limit as
\(x \rightarrow \infty \).
The table in the lemma results from the execution of the procedure described above, with \(P_N(\tau ) = \rho _N(\tau ) - 3 / (2^\tau - 1)\) and for a selection of values of \(\tau \), and so the lemma follows. \(\square \)
In Lemma
4 above, we consider
\(N = pq\) with
p,
q distinct primes drawn uniformly at random from [2,
x] as
\(x \rightarrow \infty \). In practice, we would instead like to select
\(p, q \ne p\) uniformly at random from the set of all primes of length
l bits, so that
N is an RSA integer by the definition in this paper. In practice, we may also wish to require that
N must be a 2
l bit number. Imposing such restrictions on the sizes of
p and
q should not have any significant impact on the outcome of the analysis, for the reasons elaborated on in the next section.