## Modern Elliptic Curve Factorization, Part 1

### April 23, 2010

`(define (add P1 P2 P0 N)`

(define (square n) (* n n))

(let* ((x0 (car P0)) (x1 (car P1)) (x2 (car P2))

(z0 (cdr P0)) (z1 (cdr P1)) (z2 (cdr P2))

(t1 (modulo (* (+ x1 z1) (- x2 z2)) n))

(t2 (modulo (* (- x1 z1) (+ x2 z2)) n)))

(cons (modulo (* (square (+ t2 t1)) z0) n)

(modulo (* (square (- t2 t1)) x0) n))))

`(define (double P An Ad N)`

(define (square n) (* n n))

(let* ((x (car P)) (z (cdr P))

(t1 (modulo (square (+ x z)) N))

(t2 (modulo (square (- x z)) N))

(t3 (- t1 t2)))

(cons (modulo (* t1 t2 4 Ad) N)

(modulo (* (+ (* t3 An) (* t2 Ad 4)) t3) N))))

`(define (multiply K P An Ad N)`

(cond ((zero? K) (cons 0 0)) ((= K 1) P) ((= K 2) (double P An Ad N))

(else (let loop ((ks (cdr (digits K 2))) (Q (double P An Ad N)) (R P))

(cond ((null? ks) R)

((odd? (car ks))

(loop (cdr ks) (double Q An Ad N) (add Q R P N)))

(else (loop (cdr ks) (add R Q P N) (double R An Ad N))))))))

`(define (curve12 N s)`

(let* ((u (modulo (- (* s s) 5) N))

(v (modulo (* 4 s) N)) (v-u (- v u)))

(values (modulo (* (* v-u v-u v-u) (+ u u u v)) N)

(modulo (* 4 u u u v) N)

(cons (modulo (* u u u) N)

(modulo (* v v v) N)))))

For example:

`> (define n 5569379)`

> (define s 4921134)

> (define An #f)

> (define Ad #f)

> (define P #f)

> (call-with-values

(lambda () (curve12 n s))

(lambda (a b c)

(set! An a)

(set! Ad b)

(set! P c)))

> An

3660795

> Ad

1539615

> P

(4087911 . 2770287)

> (define P2 (double P An Ad n))

> P2

(3539269 . 4477480)

> (define P3 (add P2 P P n))

> P3

(2517168 . 4993956)

> (define P4 (double P2 An Ad n))

> P4

(4683984 . 2280932)

> (define P6 (double P3 An Ad n))

> P6

(3440206 . 1480034)

> (define P7 (add P4 P3 P n))

> P7

(2544042 . 2445346)

> (define P13 (add P7 P6 P n))

> P13

(577485 . 4434222)

> (multiply 13 P An Ad n)

(577485 . 4434222)

We use `digits`

from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/t9gygODg.

[…] today’s Programming Praxis exercise we have to implement an algorithm for curve factorization. The Scheme […]

My Haskell solution (see http://bonsaicode.wordpress.com/2010/04/23/programming-praxis-modern-elliptic-curve-factorization-part-1/ for a version with comments):

Python version.

Hi Programmingpraxis

Could you tell me if my implementation is correct or not specially for multiPoint function as i was trying to reduce one more call of mulitpOint function.

[…] previous example except using Montgomery curve rather than Lenstra curve. Programmingpraxis used Montgomery curve to find the prime factorisation. I personally feel that Lenstra algorithm worked fine when […]