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

Pages: 1 2

### 5 Responses to “Modern Elliptic Curve Factorization, Part 1”

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

2. Remco Niemeijer said

```add :: Integral a => (a, a) -> (a, a) -> (a, a) -> a -> (a, a)
add (x1, z1) (x2, z2) (x0, z0) n = (f (+) z0, f (-) x0) where
f g m = (g ((x1-z1)*(x2+z2)) ((x1+z1)*(x2-z2)))^2 * m `mod` n

double :: Integral a => (a, a) -> a -> a -> a -> (a, a)
double (x,z) an ad n = (mod x' n, mod z' n) where
x' = 4 * ad * (x-z)^2 * (x+z)^2
z' = (4 * ad * (x-z)^2 + t * an) * t
t = (x+z)^2 - (x-z)^2

multiply :: Integral a => Int -> (a, a) -> a -> a -> a -> (a, a)
multiply 0 _ _  _  _ = (0,0)
multiply 1 p _  _  _ = p
multiply k p an ad n = let half = multiply (div k 2) p an ad n in
if odd k then add half (multiply (div k 2 + 1) p an ad n) p n
else double half an ad n

curve12 :: Integral a => a -> a -> (a, a, (a, a))
curve12 n s = ((v-u)^3 * (3 * u + v) `mod` n,
4 * u^3 * v `mod` n,
(u^3 `mod` n, v^3 `mod` n)) where
u = s * s - 5 `mod` n
v = 4 * s `mod` n
```
3. Mike said

Python version.

```def init( n, seed ):
u = ( seed*seed - 5 ) % n
v = 4*seed % n

num = pow(v-u, 3, n) * (3*u + v) % n
den = 4 * pow(u,3,n) * v % n

A = num, den
P = (pow(u, 3, n), pow( v, 3, n) )
return A, P

def add( p1, p2, p0, n ):
x1,z1 = p1
x2,z2 = p2
x0,z0 = p0

t1 = (x1-z1)*(x2+z2)
t2 = (x1+z1)*(x2-z2)

newx = z0 * pow( t1 + t2, 2, n ) % n
newz = x0 * pow( t1 - t2, 2, n ) % n

return newx, newz

def double( p, A, n ):
x,z = p

t1 = pow(x + z, 2, n)
t2 = pow(x - z, 2, n)
t = t1 - t2

newx = t1 * t2 * 4 * Ad % n
newz = (4 * Ad * t2 + t * An) * t % n

return newx, newz

def multiply( m, p, A, n ):
if m == 0:
return 0,0
elif m == 1:
return p
else:
q = double( p, A, n )

if m == 2:
return q

b = 1
while b < m:
b <<= 1
b >>= 2

r = p
while b:
if m&b:
q, r = double(q, A, n), add(q, r, p, n)
else:
q, r = add(r, q, p, n), double(r, A, n)
b >>= 1
return r

n,s = 5569379,4921134
A, P1 = init(n, s)
P2 = double(P1,A,n)
P4 = double(P2, A, n)
P6 = double(P3, A, n)
P13a = multiply(13,P1,A,n)

print P13, P13a, P13 == P13a
```
4. 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.

```--y^2 = x^3+ax^2+b
data Elliptic = Conelliptic Integer Integer Integer deriving (Eq,Show)
data Point = Conpoint Integer Integer deriving (Eq,Show)

addPoints (Conpoint x_1 z_1) (Conpoint x_2 z_2) (Conpoint x_0 z_0) n = let
x_3= mod ((((x_1-z_1)*(x_2+z_2)+(x_1+z_1)*(x_2-z_2))^2)*z_0) n
z_3= mod ((((x_1-z_1)*(x_2+z_2)-(x_1+z_1)*(x_2-z_2))^2)*x_0) n
in (Conpoint x_3 z_3)

doublePoint::Point->Elliptic->Point
doublePoint (Conpoint x z) (Conelliptic an ad n) = (Conpoint (mod x' n) (mod y' n))
where
where
t=(x+z)^2-(x-z)^2

multiPoint::Integer->Integer->Point->Elliptic->Point
multiPoint _ 0 _ _ = (Conpoint 0 0)
multiPoint _ 1 pOint _ = pOint
multiPoint n k pOint eCurve =let
p=multiPoint n (div k 2) pOint eCurve
in case even k of
True -> doublePoint p eCurve
_ ->  addPoints p (addPoints p pOint pOint n) pOint  n  -- for 7p i am using 6p+pOint

montgomeryCurve::Integer->Integer->[Integer]
montgomeryCurve s n = let
u=mod (s*s-5) n
v=mod (4*s) n
an=mod (((v-u)^3)*(3*u+v)) n