Elliptic curve arithmetic: Difference between revisions
Content added Content deleted
m (→{{header|REXX}}: fixed a typo, added/changed comments and whitespace, changed alignments.) |
(→{{header|Haskell}}: Added Haskell solution) |
||
Line 429: | Line 429: | ||
a + b + d = Zero |
a + b + d = Zero |
||
a * 12345 = (10.759, 35.387)</pre> |
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}}== |
=={{header|J}}== |