## 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.

Pages: 1 2

### 2 Responses to “Elliptic Curve Factorization”

1. Paul said

I tried to solve this without peeking at your solution, but I got stuck. The thing that kept tripping me up was that in a finite field, there are infinite lines that intersect two points. It seems that only one of those lines will ever intersect a third point. Your solution doesn’t involve checking infinite lines, could you explain how it works?

2. programmingpraxis said

You’ll see the solution tomorrow, which may clarify matters. Also tomorrow, you’ll see another algorithm for integer factorization using elliptic curves, which may be more to your liking.