A Heuristic Explanation

Let $N$ be a positive integer and for simplicity of exposition assume that $N=p_1\cdots p_r$ with the $p_i$ distinct primes. It follows from Lemma 2.2.6 that there is a natural isomorphism

$$f : (\mathbb{Z}/N\mathbb{Z})^* \longrightarrow (\mathbb{Z}/p_1\mathbb{Z})^* \times \cdots \times (\mathbb{Z}/p_r\mathbb{Z})^*.$$

When using Pollard's method, we choose an $a\in (\mathbb{Z}/N\mathbb{Z})^*$ , compute $a^m$ , then compute $\gcd(a^m-1,N)$ . This $\gcd$ is divisible exactly by the primes $p_i$ such that $a^m \equiv 1\pmod{p_i}$ . To reinterpret Pollard's method using the above isomorphism, let $(a_1,\ldots,a_r) = f(a)$ . Then $(a_1^m,\ldots,a_r^m) = f(a^m)$ , and the $p_i$ that divide $\gcd(a^m-1,N)$ are exactly the $p_i$ such that $a_i^m=1$ . By Theorem 2.1.19, these $p_i$ include the primes $p_j$ such that $p_j-1$ is $B$ -power smooth, where $m=\lcm (1,\ldots,m)$ .

We will not define $E(\mathbb{Z}/N\mathbb{Z}{})$ when $N$ is composite, since this is not needed for the algorithm (where we assume that $N$ is prime and hope for a contradiction). However, for the remainder of this paragraph, we pretend that $E(\mathbb{Z}/N\mathbb{Z}{})$ is meaningful and describe a heuristic connection between Lenstra and Pollard's methods. The significant difference between Pollard's method and the elliptic curve method is that the isomorphism $f$ is replaced by an isomorphism (in quotes)

$$\lq\lq g : E(\mathbb{Z}/N\mathbb{Z}{}) \rightarrow E(\mathbb{Z}/p_1\mathbb{Z}{}) \times \cdots \times E(\mathbb{Z}/p_r\mathbb{Z}{})$$''

where $E$ is $y^2=x^3+ax+1$ , and the $a$ of Pollard's method is replaced by $P=(0,1)$ . We put the isomorphism in quotes to emphasize that we have not defined $E(\mathbb{Z}/N\mathbb{Z}{})$ . When carrying out the elliptic curve factorization algorithm, we attempt to compute $m P$ and if some components of $f(Q)$ are $\O$ , for some point $Q$ that appears during the computation, but others are nonzero, we find a nontrivial factor of $N$ .