Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
add comment

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$.

share|improve this answer
2  
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. –  poncho Dec 30 '12 at 1:14
    
@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? –  Johannes Jan 9 '13 at 16:50
    
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. –  Samuel Neves Jan 9 '13 at 21:44
    
@SamuelNeves Yes, thanks. –  Johannes Jan 11 '13 at 15:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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