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.

Currently I'm working on a presentation of a paper that talks about the factorization of large numbers. In the paper elliptic curves are presented as a way to factorize large numbers. After hearing a lot about elliptic curves it's the first time that I delve into the details of elliptic curves and I'm a bit bit baffled to say the least.

My question is: why are elliptic curves suited for the factorization of numbers?

In the paper it's stated that for an integer number $n$ there exist various suited elliptic curves that can be used for its factorization, meaning that checking multiple elliptic curves for a number can be parallelized. But still, what is the real reason (from a mathematical point of view) why elliptic curves are used for this kind of task?

share|improve this question
add comment

1 Answer

up vote 6 down vote accepted

It's probably best to understand Lenstra's Elliptic Curve factorization algorithm by way of contrast with its predecessors, the Pollard's p-1 method, the Williams' p+1 method and the Cyclotomic Polynomial method of Bach and Shallit.

These are all Algebraic-group factorisation algorithms which require you to select a stage 1 bound $B_1$ and stage 2 bound $B_2$ where $B_1<B_2$.

The most common way for Pollard's p-1 method to fail is if none of the primes dividing the composite N to be factored have the order of the group of multiplicative elements (i.e p-1) able to be written as a product of prime powers smaller than $B_1$ and at most one prime between $B_1$ and $B_2$. Numbers having this representation are rare and can be loosely termed "smooth".

This is purely a characteristic of the composite to be factored and without knowledge of the factors you don't know whether the p-1 method is doomed to failure.

The Williams' p+1 method uses the multiplicative group of a quadratic extension of N which (if successfully chosen) has order p+1. So it fails if none of the $p+1$s are smooth .

The Cyclotomic Polynomial method succeeds if let's say $p^2+p+1$ or more complex expressions are smooth but these numbers are getting larger than $p$ and the chance that they are smooth (unless N has a special structure) is rapidly decreasing.

What would be nice would be to have an effectively unlimited number of different groups with different orders that we can try where there's nothing stopping the group orders being smooth and the group operations are reasonably quick. That's what Lenstra's Elliptic Curve method delivers.

The way it works is that you choose a random $\sigma$ which specifies an elliptic curve where the orders of the multiplicative groups is somewhere in the range $p+1 \pm \sqrt p$. The algorithm will succeed if for one of the curves you try, the order is smooth.

In terms a layman might understand, when Pollard's p-1 algorithm was discovered, we could all of a sudden quickly factorize a whole swathe of numbers where p-1 is smooth but we were still stuck on other numbers. When Williams' p+1 algorithm came along then we could now factorize a whole lot more numbers where p+1 is smooth but we were still stuck on lots of numbers. When Bach and Shallit's Cyclotomic Polynomial method came along, a few more numbers were factorizable but it's clear that the effectiveness of each successive algorithm was diminishing. With elliptic curves, each $\sigma$ value is essentially making available a new algorithm as good as p-1 which works if $p+1-a$ is smooth for some $|a| \lt \sqrt p$. Unlike previous algorithms, we don't know what $a$ will be until the factor has been found. Now we no longer have to worry about the prime factors being small but "hard". The difficulty is purely dependent on their size.

share|improve this answer
    
Perfect, thank you very much for your time and answer! This is actually the answer I was looking for. –  Pete Nov 4 '13 at 15:44
    
I also have to note that your link to the wiki page for Algebraic-group factorization algorithms was very useful. Thank you very much! –  Pete Nov 4 '13 at 15:55
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.