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
`

An elliptic curves is a Genus I curve given by the equation
y^{2} = x^{3} + ax^{2} + 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.

- 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. - Choose random integers b, x
_{1}, y_{1}between 1 and n. - Take the cubic curve y
^{2}= x^{3}+ bx + c, where c = y_{1}^{2}- x_{1}^{3}- bx_{1}. - Check that gcd(4b
^{3}+27c^{2},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.) - 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
_{2}(n)]. - Add the point (x
_{1}, y_{1}) 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.

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_{2}k) time. First, one does
log_{2}k additions of the point (call it P) to itself,
generating the partial sums

P

P

P

P

.

.

.

P

Then kP is simply the sum of the points P_{i} for which
the *i*th bit of k in binary form is 1.

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