Elliptic Curves Factoring Fun

Factor
Completely Factor Show Curve Show K Show Partials Show Calculations (Not yet implemented)

Input

You can input both numbers and arithmetic expressions. Supported operators are +, -, *, /, ^, and !. (Note: you must be sure that the division will produce an integer otherwise the results are not guaranteed). Examples include:
(2^112)-1
9!-1
((2^22)*(3^22))-1

Elliptic Curves

An elliptic curves is a Genus I curve given by the equation y2 = x3 + ax2 + bx + c. We define a simple set operation @ on these curves which is performed as follows: for any two points A and B, draw a line which intersects them. This line will interset the curve at one more point C. A@B is then defined to be C.

This set operation unfortunately lacks some properties that we would like, such as containing a zero element in the set. We fix this by defining the operation + on elliptic curves to be (A*B)*O, or some fixed point O. This fixed point O then becomes the zero element and the set of (rational) points on the curve become a group under this operation.

It turns out that if one does the arithmetic requires for these operations mod p for some prime p that one still gets a point on the curve (provided that one started with a rational point).

Lenstra's algorithm takes advantage of this fact by doing the arithmetic mod n, for the composite number that we wish to factor n. While the operation is no longer guaranteed to give us a point on the curve, this isn't a problem. In fact, it's what we're hoping for. When the arithmetic fails, it will be because we have found some number which is not relatively prime to n. In most cases, we are lucky enough for our number not to be 0 or n, so that we will have found a non-trivial factor.

The Algorithm

Let n > 34 be the number that we want to factor.
  1. Check that gcd(n, 6) = 1 (that is, that n is not divisible by either 2 or 3) and that n cannot be represented as ab for some integers a and b.
  2. Choose random integers b, x1, y1 between 1 and n.
  3. Take the cubic curve y2 = x3 + bx + c, where c = y12 - x13 - bx1.
  4. Check that gcd(4b3+27c2,n) is 1. (If it is n, go back to set 2. If it is strictly between 1 and n, it is then a non-trivial factor of n and the algorithm is done.)
  5. Choose a number k which is a product of small primes. An easy way to get such a k is to choose k = LCM[1,2,3,...,log2(n)].
  6. Add the point (x1, y1) to itself k times. For every addition, an gcd will have to be calculated in order to ensure that taking an inverse (mod n) will be possible. If any of these gcds are strictly between 1 and n, it is a non-trivial factor. If any of them are n, the value of k was too high. Either pick a smaller k or pick a new curve and go back to the appropriate step.

Notes

It should be noted that performing k additions of the point to itself is extremely time-consuming if it is done by actually doing k additions. Thankfully, there is a much more efficient way that operates in O(log2k) time. First, one does log2k additions of the point (call it P) to itself, generating the partial sums

P0 = P
P1 = 2P0 = 2P
P2 = 2P1 = 22P
P3 = 2P2 = 23P
P4 = 2P3 = 24P
.
.
.
Plog2k = 2P(log2k)-1 = 2log2kP

Then kP is simply the sum of the points Pi for which the ith bit of k in binary form is 1.


Christopher Tomaras Lansdown
Last modified: Tue May 8 15:19:46 EDT 2001