In Wikipedia, there is an article explaining Lenstra's factorization algorithm. As far as I got it, we choose some $e \in \mathbb{N}$ and a point $P$ on the curve and then calculate $eP$. While calculating, we must invert elements, and if that does not work, we are rewarded with a factorization.

So far, so good. Now, Wikipedia (and some other books) suggest that $e=B!$ for some small $B \in \mathbb{N}$. Can someone please explain why this is so good? Also, why is there a relation in the choice of $B$ to Pollard's $p-1$ algorithm?


1 Answer 1


It becomes clear once you understand what $p-1$ and ECM are doing. I'll start with $p-1$, since it is simpler.

Suppose the number you want to factor, $n$, is the product of two primes: $p$ and $q$. If we knew $p-1$, we could get $p$ from $n$ by doing

$$ \gcd(a^{p-1} - 1 \bmod n, n) = p. $$

This works because by working modulo $n$, we're working "in parallel" modulo $p$ and modulo $q$. And modulo $p$, we get $a^{p-1} - 1 = 0 \bmod p$ (for nonzero $a$) by Fermat's little theorem. So $a^{p-1} - 1 \bmod n$ is going to be 0 modulo $p$, but not modulo $q$, and the $\gcd$ gives us a factorization of $n$.

However, we don't really know $p-1$ — if we did, we wouldn't be looking for $p$ — and that puts a dent in our plans. There is an alternative route, however: if we can find a multiple of $p-1$, that works too: $$ a^{k(p-1)} - 1 \bmod p \equiv (a^{p-1})^k - 1 \bmod p \equiv 1^k - 1 \bmod p = 0 \bmod p. $$

So what Pollard's $p-1$ does is select an exponent that is likely to contain every single factor of $p-1$. An easy way to do this, that works as long as $p-1$ only has small-ish factors, is simply to make the exponent the product of all primes: $2\cdot3\cdot5\cdot7\ldots\cdot B_1$, where $B_1$ is our upper bound. This, however, misses power-of-prime factors, such as $2^2$ or $3^5$. So another exponent that catches everything is the factorial of $B_1$: that one is certain to catch every possible factor up to $B_1$!

Some observations about $p-1$ leads us to ECM. $p-1$ is the order of the group formed by the integers modulo $p$, denoted by $\mathbb{F}_p$. Further, if the order of $\mathbb{F}_p$ only has small factors, we can find $p$ by the aforementioned exponentiation. It turns out this generalizes to other mathematical groups. In particular, the group of points in an elliptic curve modulo $p$ is parameterized by two additional numbers $a$ and $b$:

$$ E_{a,b} = \{ (x, y) : y^2 = x^3 + a x + b \pmod{p} \} $$

Each curve (parameterized by a and b) modulo $p$ has an order ($\#E$, analogous to $p-1$ above) in the range $$ p + 1 - 2\sqrt{p} < \#E < p + 1 + 2\sqrt{p}. $$ Further, for each order in that interval, there is an $(a,b)$ tuple that yields it.

Suppose we pick a random elliptic curve $E_{a,b}$, and run it modulo $n$ (again, "in parallel" in both $p$ and $q$). Picking a random point in the curve, $P$, and multiplying it by $\#E$ results in the point at infinity (the elliptic curve analogous of 0):

$$ \#E\cdot P = \infty $$

This special point, usually represented as $(0,1)$, triggers divisions by $0 \bmod p$ but not $\bmod~q$, and that nets us a factor. The logic for picking the exponent is the same as $p-1$: every prime and prime power up to $B_1$, and hope for a hit.

Besides the factorial, another good way to pick the exponent is the lowest common multiple of every integer up to $B_1$; this yields every prime power lower than $B_1$, and is much smaller than the factorial of $B_1$.

  • 2
    $\begingroup$ To add to the above correct answer, one problem that the factorial has is that it overrepresents small factors. For example, 10000! (which is a relatively small multiplier; it's limited to finding orders that have no prime factors > 10000) has $2^{9995}$ as a factor; obviously, the order cannot have that as a factor. Including the extra powers of 2 won't prevent us finding the factor; however, the additional EC additions it implies is a waste of time. Samuel's last suggestion is better; it doesn't waste time on large powers of small factors. $\endgroup$
    – poncho
    Dec 30, 2012 at 1:14
  • $\begingroup$ @SamuelNeves Many Thanks! Just to be sure: In Pollard, we try a versatile (has many primes in it) exponent in order to get a multiple of $p-1$. In ECM, we try a versatile factor in order to get a multiple of $\#E$? Can you please check this? $\endgroup$
    – Johannes
    Jan 9, 2013 at 16:50
  • $\begingroup$ I am unsure what you mean by "factor" in the ECM case; if you mean the integer multiplied by P, then yes, that's it. $\endgroup$ Jan 9, 2013 at 21:44

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.