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.

Advertisements

Programming Praxis – 145 Puzzle

In today’s Programming Praxis exercise we have to solve a math puzzle. The provided solution is 15 lines, not counting the parser to evaluate the generated strings. Let’s see if we can bring that down a bit.

Some imports:

import Control.Applicative
import qualified Data.List.Key as K
import Text.Parsec

Generating the expressions is pretty simple. If we have at least one digit, prepend the first digit to all the possible expressions for the remaining digits with either nothing or a plus or minus sign in between. If we only have one digit, that digit is the only option.

exprs :: String -> [String]
exprs (x:y:ys) = [x:o++z | o <- ["","+","*"], z <- exprs $ y:ys]
exprs xs       = [xs]

Since we now have more control over the input string (no spaces, subtraction or division), we can make last week’s parser slightly more compact.

eval :: String -> Int
eval = either (const 0) id . parse expr "" where
    expr = chainl1 term ((+) <$ char '+')
    term = chainl1 (read <$> many1 digit) ((*) <$ char '*')

Finding the required statistics is pretty trivial. Just group the expressions by their evaluated results and find the most common one.

main :: IO ()
main = do let mf = K.maximum length . K.group snd . K.sort snd .
                   liftA2 zip id (map eval) $ exprs ['1'..'9']
          print (snd $ head mf, length mf)
          mapM_ putStrLn $ map fst mf

Six lines, not counting the parser. Not bad.

Programming Praxis – Expression Evaluation

In today’s Programming Praxis exercise our task to write a parser for simple mathematical expressions. Let’s get started, shall we?

Some imports:

import Control.Applicative
import Text.Parsec hiding ((<|>))

We’re going to be using a somewhat different approach than the provided Scheme solution. Rather than doing everything ourselves, we will use the Parsec library, which is the go-to solution for writing parsers in Haskell. This, however, results in a small limitation. Parsec is a parser combinator library, and parser combinators cannot deal with left-recursive grammars. The grammar in the assignment is left-recursive, because if we were to enter the rule expr = expr + term (as I did in my first attempt in solving this), our program will enter an infinite loop. Fortunately, left-recursive grammars can be fairly easily rewritten using the chain functions in Parsec.

An expression is one or more terms, separated by addition and subtraction operators.

expr = chainl1 term ((+) <$ char '+' <|> (-) <$ char '-')

A term works just like an expression, but with multiplication and divison.

term = chainl1 fact ((*) <$ char '*' <|> div <$ char '/')

Factors need no change from the specified grammar: they’re either numbers or expressions in parentheses.

fact = read <$> many1 digit <|> char '(' *> expr <* char ')'

Evaluating an expression is trivial. The only extra step is to filter out all the spaces, since they have not been defined in the grammar but are present in the test cases.

eval :: String -> Int
eval = either (error . show) id . parse expr "" . filter (/= ' ')

A quick test shows that our rewritten grammar passes all of the test cases correctly:

main :: IO ()
main = mapM_ print [eval "6+2"            == 8
                   ,eval "6-2"            == 4
                   ,eval "6*2"            == 12
                   ,eval "6/2"            == 3
                   ,eval "6 * 2"          == 12
                   ,eval "2+3*4"          == 14
                   ,eval "2*3+4"          == 10
                   ,eval "2+3+4"          == 9
                   ,eval "2-3-4"          == -5
                   ,eval "2*3*4"          == 24
                   ,eval "(2+3)*4"        == 20
                   ,eval "(2*3)+4"        == 10
                   ,eval "2+(3*4)"        == 14
                   ,eval "2*(3+4)"        == 14
                   ,eval "12 * (34 + 56)" == 1080
                   ]

Using a parser library and slightly rewriting the grammar reduces the amount of required lines from 48 to 4. That’s a good trade-off in my book.

Programming Praxis – Minimum Spanning Tree: Prim’s Algorithm

In today’s Programming Praxis exercise we have to implement an algorithm for finding the minimum spanning tree of a graph. The Scheme solution weighs in at 15 lines, so let’s see if we can do better.

As usual, some imports:

import Data.List
import qualified Data.List.Key as K

Both the Scheme solution and the pseudocode algorithm on Wikipedia take both a list of vertices and a list of edges as input, but since the list of vertices is implicitly defined in the edges there’s really no point in specifying it separately. To get the starting vertex, we just take the first vertex of the first edge. Other than that, we do pretty much what the pseudocode algorithm says: check if there’s an edge with one connected and one unconnected point. If multiple exist, add the shortest. Add the unconnected vertex to the list of connected ones. Stop if there are no more edges with unconnected vertices.

prim :: (Eq a, Ord b) => [(a, a, b)] -> [(a, a, b)]
prim es = f [(\(v,_,_) -> v) $ head es] [] where
    f vs t = if null r then t else f (union vs [x,y]) (m:t) where
        r = filter (\(a,b,_) -> elem a vs /= elem b vs) es
        m@(x,y,_) = K.minimum (\(_,_,c) -> c) r

A quick test shows we get the same result as the Scheme version:

main :: IO ()
main = print $ prim [('A', 'D',  5), ('A', 'B', 7), ('B', 'D', 9)
                    ,('B', 'C',  8), ('C', 'E', 5), ('B', 'E', 7)
                    ,('D', 'E', 15), ('D', 'F', 6), ('E', 'F', 8)
                    ,('F', 'G', 11), ('E', 'G', 9)]

And with that we’ve reduced a 15-line solution to four lines. Not bad.