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.

About these ads

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 615 other followers

%d bloggers like this: