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.