arithmoi-0.9.0.0: Efficient basic number-theoretic functions.

Copyright(c) 2017 Andrew Lelechenko
LicenseMIT
MaintainerAndrew Lelechenko <andrew.lelechenko@gmail.com>
Safe HaskellNone
LanguageHaskell2010

Math.NumberTheory.Curves.Montgomery

Description

Arithmetic on Montgomery elliptic curve.

Synopsis

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.

Instances
KnownNat n => Eq (Point a24 n) Source #

In projective space Points are equal, if they are both at infinity or if respective ratios pointX / pointZ are equal.

Instance details

Defined in Math.NumberTheory.Curves.Montgomery

Methods

(==) :: Point a24 n -> Point a24 n -> Bool #

(/=) :: Point a24 n -> Point a24 n -> Bool #

(KnownNat a24, KnownNat n) => Show (Point a24 n) Source #

For debugging.

Instance details

Defined in Math.NumberTheory.Curves.Montgomery

Methods

showsPrec :: Int -> Point a24 n -> ShowS #

show :: Point a24 n -> String #

showList :: [Point a24 n] -> ShowS #

pointX :: Point a24 n -> Integer Source #

Extract x-coordinate.

pointZ :: Point a24 n -> Integer Source #

Extract z-coordinate.

pointN :: forall a24 n. KnownNat n => Point a24 n -> Integer Source #

Extract modulo of the curve.

pointA24 :: forall a24 n. KnownNat a24 => Point a24 n -> Integer Source #

Extract (a + 2) / 4, where a is a coefficient in curve's equation.

data SomePoint where Source #

Point on unknown curve.

Constructors

SomePoint :: (KnownNat a24, KnownNat n) => Point a24 n -> SomePoint 

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.

double :: (KnownNat a24, KnownNat n) => Point a24 n -> Point a24 n Source #

Multiply by 2.

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.

multiply :: (KnownNat a24, KnownNat n) => Word -> Point a24 n -> Point a24 n Source #

Multiply by given number, using binary algorithm.