Copyright | (c) 2017 Andrew Lelechenko |
---|---|

License | MIT |

Maintainer | Andrew Lelechenko <andrew.lelechenko@gmail.com> |

Stability | Provisional |

Portability | Non-portable (GHC extensions) |

Safe Haskell | None |

Language | Haskell2010 |

Arithmetic on Montgomery elliptic curve.

- data Point (a24 :: Nat) (n :: Nat)
- pointX :: Point a24 n -> Integer
- pointZ :: Point a24 n -> Integer
- pointN :: forall a24 n. KnownNat n => Point a24 n -> Integer
- pointA24 :: forall a24 n. KnownNat a24 => Point a24 n -> Integer
- data SomePoint where
- newPoint :: Integer -> Integer -> Maybe SomePoint
- add :: KnownNat n => Point a24 n -> Point a24 n -> Point a24 n -> Point a24 n
- double :: (KnownNat a24, KnownNat n) => Point a24 n -> Point a24 n
- multiply :: (KnownNat a24, KnownNat n) => Word -> Point a24 n -> Point a24 n

# Documentation

data Point (a24 :: Nat) (n :: Nat) Source #

We use the Montgomery form of elliptic curve: b Y² = X³ + a X² + X (mod n). See Eq. (10.3.1.1) at p. 260 of Speeding the Pollard and Elliptic Curve Methods of Factorization by P. L. Montgomery.

Switching to projective space by substitutions Y = y / z, X = x / z, we get b y² z = x³ + a x² z + x z² (mod n). The point on projective elliptic curve is characterized by three coordinates, but it appears that only x- and z-components matter for computations. By the same reason there is no need to store coefficient b.

That said, the chosen curve is represented by a24 = (a + 2) / 4 and modulo n at type level, making points on different curves incompatible.

Point on unknown curve.

newPoint :: Integer -> Integer -> Maybe SomePoint Source #

`newPoint`

`s`

`n`

creates a point on an elliptic curve modulo `n`

, uniquely determined by seed `s`

.
Some choices of `s`

and `n`

produce ill-parametrized curves, which is reflected by return value `Nothing`

.

We choose a curve by Suyama's parametrization. See Eq. (3)-(4) at p. 4 of Implementing the Elliptic Curve Method of Factoring in Reconfigurable Hardware by K. Gaj, S. Kwon et al.

add :: KnownNat n => Point a24 n -> Point a24 n -> Point a24 n -> Point a24 n Source #

If `p0`

+ `p1`

= `p2`

, then `add`

`p0`

`p1`

`p2`

equals to `p1`

+ `p2`

.
It is also required that z-coordinates of `p0`

, `p1`

and `p2`

are coprime with modulo
of elliptic curve; and x-coordinate of `p0`

is non-zero.
If preconditions do not hold, return value is undefined.

Remarkably such addition does not require `KnownNat`

`a24`

constraint.

Computations follow Algorithm 3 at p. 4 of Implementing the Elliptic Curve Method of Factoring in Reconfigurable Hardware by K. Gaj, S. Kwon et al.