Anonymous user
Elliptic curve arithmetic: Difference between revisions
→{{header|Haskell}}: Added Haskell solution
m (→{{header|REXX}}: fixed a typo, added/changed comments and whitespace, changed alignments.) |
(→{{header|Haskell}}: Added Haskell solution) |
||
Line 429:
a + b + d = Zero
a * 12345 = (10.759, 35.387)</pre>
=={{header|Haskell}}==
First, some seful imports:
<lang haskell>import Data.Monoid
import Control.Monad (guard)
import Test.QuickCheck (quickCheck)</lang>
The datatype for a point on an elliptic curve with exact zero:
<lang haskell>import Data.Monoid
data Elliptic = Elliptic Double Double | Zero
deriving Show
instance Eq Elliptic where
p == q = dist p q < 1e-14
where
dist Zero Zero = 0
dist Zero p = 1/0
dist p Zero = 1/0
dist (Elliptic x1 y1) (Elliptic x2 y2) = (x2-x1)^2 + (y2-y1)^2
inv Zero = Zero
inv (Elliptic x y) = Elliptic x (-y)</lang>
Points on elliptic curve form a monoid:
<lang haskell>instance Monoid Elliptic where
mempty = Zero
mappend Zero p = p
mappend p Zero = p
mappend p@(Elliptic x1 y1) q@(Elliptic x2 y2)
| p == inv q = Zero
| p == q = mkElliptic $ 3*x1^2/(2*y1)
| otherwise = mkElliptic $ (y2 - y1)/(x2 - x1)
where
mkElliptic l = let x = l^2 - x1 - x2
y = l*(x1 - x) - y1
in Elliptic x y</lang>
Examples given in other solutions:
<lang haskell>ellipticX b y = Elliptic (qroot (y^2 - b)) y
where qroot x = signum x * abs x ** (1/3)</lang>
<pre>λ> let a = ellipticX 7 1
λ> let b = ellipticX 7 2
λ> a
Elliptic (-1.8171205928321397) 1.0
λ> b
Elliptic (-1.4422495703074083) 2.0
λ> let c = a <> b
λ> c
Elliptic 10.375375389201409 (-33.524509096269696)
λ> let d = inv c
λ> c <> d
Zero
λ> a <> b <> d
Zero</pre>
Extra credit: multiplication.
1. direct monoidal solution:
<lang haskell>mult :: Int -> Elliptic -> Elliptic
mult n = mconcat . replicate n</lang>
2. efficient recursive solution:
<lang haskell>n `mult` p
| n == 0 = Zero
| n == 1 = p
| n == 2 = p <> p
| n < 0 = inv ((-n) `mult` p)
| even n = 2 `mult` ((n `div` 2) `mult` p)
| odd n = p <> (n -1) `mult` p</lang>
<pre>λ> 12345 `mult` a
Elliptic 10.758570529320476 35.387434774280486</pre>
===Testing===
We use QuickCheck to test general properties of points on arbitrary elliptic curve.
<lang haskell>-- for given a, b and x returns a point on the elliptic curve (it the point exists)
ellipticY a b Nothing = Just Zero
ellipticY a b (Just x) =
do let y2 = x**3 + a*x + b
guard (y2 > 0)
return $ Elliptic x (sqrt y2)
associativity a b x1 x2 x3 =
let p = ellipticY a b
in (p x1 <> p x2) <> p x3 == p x1 <> (p x2 <> p x3)
commutativity a b x1 x2 =
let p = ellipticY a b
in p x1 <> p x2 == p x2 <> p x1</lang>
<pre>λ> quickCheck associativity
+++ OK, passed 100 tests.
λ> quickCheck commutativity
+++ OK, passed 100 tests.</pre>
=={{header|J}}==
| |||