Programming Praxis – Modern Elliptic Curve Factorization, Part 1

Today marks the 1-year anniversary of this blog. What better way to celebrate than to do another programming exercise?

In today’s Programming Praxis exercise we have to implement an algorithm for curve factorization. The Scheme solution is 30 lines. Let’s see if we can do any better.

Since the formulas for calculating the x and z coordinates of the addition result are nearly identical, we can factor it out into a function.

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

For doubling, we could factor out the first three terms of the two multiplications, but it would barely save any space.

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

Multiplication can be done through some simple recursion.

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

Calculating the curve is just executable math.

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

And, as usual, a test to see if everything is working correctly.

main :: IO ()
main = do let (n, s) = (5569379, 4921134)
          let (an, ad, p) = curve12 n s
          let p2 = double p an ad n
          let p3 = add p2 p p n
          let p4 = double p2 an ad n
          let p6 = double p3 an ad n
          let p7 = add p4 p3 p n
          let p13 = add p7 p6 p n
          print $ p2 == (3539269, 4477480)
          print $ p3 == (2517168, 4993956)
          print $ p4 == (4683984, 2280932)
          print $ p6 == (3440206, 1480034)
          print $ p7 == (2544042, 2445346)
          print $ p13 == (577485, 4434222)
          print $ multiply 13 p an ad n == p13

That leaves us with 16 lines, just over half the size of the Scheme solution, which is better than I anticipated since math problems tend to be hard to achieve major savings on.

About these ads

Tags: , , , , , , , ,

One Response to “Programming Praxis – Modern Elliptic Curve Factorization, Part 1”

  1. Kwezan Says:

    Hi,
    It would be nice to see your “bonsai” solutions to “Modern Elliptic Curve Factorization Part II” and “Integer Factorization”
    excercises.

    Best regards,
    Kwezan

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 35 other followers

%d bloggers like this: