Elliptic Curves Factoring Fun

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 y² = x³ + ax² + 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

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 a^b for some integers a and b.
2. Choose random integers b, x₁, y₁ between 1 and n.
3. Take the cubic curve y² = x³ + bx + c, where c = y₁² - x₁³ - bx₁.
4. Check that gcd(4b³+27c²,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,...,log₂(n)].
6. Add the point (x₁, y₁) 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(log₂k) time. First, one does log₂k additions of the point (call it P) to itself, generating the partial sums

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