Elliptic Curves

July 28, 2009

We represent the curve y2x3 + ax + b (mod m) as the list '(a b m); the point at infinity is the list '(0 1 0) and any other point (x,y) on the curve is represented as the list '(x y 1). The basic operation is addition of two points on the curve:

(define (ecm-plus ecm p1 p2)
  (define a (car ecm)) (define b (cadr ecm)) (define m (caddr ecm))
  (define x car) (define y cadr) (define z caddr)
  (define (sq x) (* x x)) (define infinity (list 0 1 0))
  (define (inv x) ; modular inverse
    (let loop ((x (modulo x m)) (a 1))
      (cond ((zero? x) #f) ((= x 1) a)
            (else (let ((q (- (quotient m x))))
                    (loop (+ m (* q x)) (modulo (* q a) m)))))))
  (define (return n d)
    (let ((d (inv d)))
      (if (not d) #f
        (let ((x3 (modulo (- (* n d n d) (x p1) (x p2)) m)))
          (list x3 (modulo (- (* n d (- (x p1) x3)) (y p1)) m) 1)))))
  (cond ((or (not (pair? p1)) (not (pair? p2))) #f)
        ((zero? (z p1)) p2) ((zero? (z p2)) p1)
        ((= (x p1) (x p2))
          (if (zero? (modulo (+ (y p1) (y p2)) m)) infinity
            (return (+ (* 3 (sq (x p1))) a) (* 2 (y p1)))))
        (else (return (- (y p2) (y p1)) (- (x p2) (x p1))))))

This follows the addition law closely, and is careful to signal an error if the modular inverse is undefined. The negation, subtraction and doubling functions are all trivial uses of addition:

(define (ecm-negate ecm p)
  (define x car) (define y cadr) (define z caddr)
  (list (x p) (modulo (- (y p)) (caddr ecm)) (z p)))

(define (ecm-double ecm p) (ecm-plus ecm p p))

(define (ecm-minus ecm p1 p2) (ecm-plus ecm p1 (ecm-negate ecm p2)))

Multiplication uses the Russian peasant algorithm, known to mathematicians as “double-and-add,” to perform repeated additions:

(define (ecm-times ecm n p)
  (cond ((= n 1) p)
        ((odd? n) (ecm-plus ecm p (ecm-times ecm (quotient n 2) (ecm-double ecm p))))
        (else (ecm-times ecm (quotient n 2) (ecm-double ecm p)))))

Here are some examples:

> (ecm-plus '(4 4 5) '(1 2 1) '(4 3 1))
(4 2 1)
> (ecm-negate '(4 4 5) '(1 2 1))
(1 3 1)
> (ecm-double '(4 4 5) '(1 2 1))
(2 0 1)
> (ecm-minus '(4 4 5) '(4 2 1) '(4 3 1))
(1 2 1)
> (ecm-times '(4 4 5) 3 '(1 2 1))
(1 3 1)
> (ecm-times '(4 4 5) 4 '(1 2 1))
(0 1 0)
> (ecm-times '(4 4 5) 5 '(1 2 1))
(1 2 1)

You can run the code at http://programmingpraxis.codepad.org/rNlg4Pgt.

About these ads

Pages: 1 2

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: