## Elliptic Curve Factorization

### July 31, 2009

Here is our function to factor numbers using a vastly simplified version of the elliptic curve algorithm, based on repeated elliptic addition until the slope becomes uncomputable:

```(define (ecm-factor n)   (let* ((a (randint n)) (b (- a)) (ecm (list a b n)) (p '(1 1 1)))     (let loop ((p p) (q (ecm-plus ecm p p)))       (if (or (not q) (equal? '(0 1 0) q))           (let ((g (gcd (- (car p) 1) n)))             (if (= g 1) (ecm-factor n) g))           (loop q (ecm-plus ecm q '(1 1 1)))))))```

This relies on the `#f` returned by `ecm-plus` if the elliptic addition fails. When that happens, or if the elliptic addition happens to return the point at infinity, the function calculates the greatest common divisor and returns a factor. Otherwise, it loops back for the next elliptical addition.

The factorization of 455839 = 599 × 761 looks like this (it finds 761 when we run it, but may find 599 depending on the elliptic curve selected by your random number generator):

```> (ecm-factor 455839) 761```

We use `rand` and `randint` from the Standard Prelude and elliptic addition from the prior exercise. You can run the code at http://programmingpraxis.codepad.org/BLfW5dKY.