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 […]