2
$\begingroup$

In Lenstra's ECM algorithm, $\#E(\mathbb{F}_{p})$ is required to have small prime factors. Why is this so?

I understand that the p-1 method is efficient for factoring N with small factors. The ECM algorithm replaces the $\mathbb{Z}/p\mathbb{Z}$ group with points on an elliptic curve, both groups having finite cardinality. Why isn't there a restraint on the former?

$\endgroup$
4
$\begingroup$

In Lenstra's ECM algorithm, $\#E(\mathbb{F}_{p})$ is required to have small prime factors. Why is this so?

Actually, it is not required to have small prime factors; it does work better (that is, succeeds quicker) if it happens to have small factors. To explain it fuller, we'll look at ECM and the p-1 method, which brings up your comment:

I understand that the p-1 method is efficient for factoring N with small factors.

Actually, what it is good at is factoring N that happens to have a prime factor p where $p-1$ is smooth; that is, consists only of small factors.

The p-1 and the ECM method both work this way: we take our composite number $n = pq$ (where, in general, can have more than two prime factors), and set secret values $p - \epsilon_1$, $q - \epsilon_2$. Then, we keep on guessing prime factors of $p - \epsilon_1$, $q - \epsilon_2$; if we guess all of the prime factors of one of them, then we immediately get the factorization (and other than time, there's no penalty for making incorrect guesses).

That's what they have in common; now, here's the difference between p-1 and ECM. With the p-1 method, we always have $\epsilon_1 = \epsilon_2 = 1$ (and that's what having $p-1$ smooth is important; we'll guess small factors, and so $p-1$ works when all the factors are small). Now, with ECM, $\epsilon_1, \epsilon_2$ are small (compared to the magnitude of $p, q$), but can vary to a large extent (depending on the curve).

And, that's the advantage of ECM: the p-1 method is entirely dependent on something beyond the algorithms control. If both p-1 and q-1 contains a large (unguessable) factor, it's out of luck, and there's nothing the algorithm can do about it. With ECM, we can try lots of different curves (with different $\epsilon_1, \epsilon_2$ values), and we might get lucky with one.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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