{- |
module: Factor.Ec
description: Elliptic curve factorization and primality proving
license: MIT

maintainer: Joe Leslie-Hurd <joe@gilith.com>
stability: provisional
portability: portable
-}
module Factor.Ec
where

import System.Random (RandomGen)
import qualified System.Random as Random

import Factor.Gfpx (Gfpx)
import qualified Factor.Gfpx as Gfpx
import Factor.Prime (Prime,Gfp)
import qualified Factor.Prime as Prime
import Factor.Util
import Factor.Zx ()

-------------------------------------------------------------------------------
-- Elliptic curves
-------------------------------------------------------------------------------

data Curve =
    Curve {Curve -> Prime
kCurve :: Prime, Curve -> Prime
aCurve :: Gfp, Curve -> Prime
bCurve :: Gfp}
  deriving (Curve -> Curve -> Bool
(Curve -> Curve -> Bool) -> (Curve -> Curve -> Bool) -> Eq Curve
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Curve -> Curve -> Bool
$c/= :: Curve -> Curve -> Bool
== :: Curve -> Curve -> Bool
$c== :: Curve -> Curve -> Bool
Eq,Eq Curve
Eq Curve
-> (Curve -> Curve -> Ordering)
-> (Curve -> Curve -> Bool)
-> (Curve -> Curve -> Bool)
-> (Curve -> Curve -> Bool)
-> (Curve -> Curve -> Bool)
-> (Curve -> Curve -> Curve)
-> (Curve -> Curve -> Curve)
-> Ord Curve
Curve -> Curve -> Bool
Curve -> Curve -> Ordering
Curve -> Curve -> Curve
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: Curve -> Curve -> Curve
$cmin :: Curve -> Curve -> Curve
max :: Curve -> Curve -> Curve
$cmax :: Curve -> Curve -> Curve
>= :: Curve -> Curve -> Bool
$c>= :: Curve -> Curve -> Bool
> :: Curve -> Curve -> Bool
$c> :: Curve -> Curve -> Bool
<= :: Curve -> Curve -> Bool
$c<= :: Curve -> Curve -> Bool
< :: Curve -> Curve -> Bool
$c< :: Curve -> Curve -> Bool
compare :: Curve -> Curve -> Ordering
$ccompare :: Curve -> Curve -> Ordering
$cp1Ord :: Eq Curve
Ord)

data Point =
    Point {Point -> Prime
xPoint :: Gfp, Point -> Prime
yPoint :: Gfp}
  | Infinity
  deriving (Point -> Point -> Bool
(Point -> Point -> Bool) -> (Point -> Point -> Bool) -> Eq Point
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Point -> Point -> Bool
$c/= :: Point -> Point -> Bool
== :: Point -> Point -> Bool
$c== :: Point -> Point -> Bool
Eq,Eq Point
Eq Point
-> (Point -> Point -> Ordering)
-> (Point -> Point -> Bool)
-> (Point -> Point -> Bool)
-> (Point -> Point -> Bool)
-> (Point -> Point -> Bool)
-> (Point -> Point -> Point)
-> (Point -> Point -> Point)
-> Ord Point
Point -> Point -> Bool
Point -> Point -> Ordering
Point -> Point -> Point
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: Point -> Point -> Point
$cmin :: Point -> Point -> Point
max :: Point -> Point -> Point
$cmax :: Point -> Point -> Point
>= :: Point -> Point -> Bool
$c>= :: Point -> Point -> Bool
> :: Point -> Point -> Bool
$c> :: Point -> Point -> Bool
<= :: Point -> Point -> Bool
$c<= :: Point -> Point -> Bool
< :: Point -> Point -> Bool
$c< :: Point -> Point -> Bool
compare :: Point -> Point -> Ordering
$ccompare :: Point -> Point -> Ordering
$cp1Ord :: Eq Point
Ord)

instance Show Curve where
  show :: Curve -> String
show Curve
e = String
"y^2 = " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Zx -> String
forall a. Show a => a -> String
show Zx
f String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" (mod " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Prime -> String
forall a. Show a => a -> String
show Prime
k String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
")"
    where
      f :: Zx
f = Prime -> Gfpx -> Zx
Gfpx.toSmallestZx Prime
k (Curve -> Gfpx
rhs Curve
e)
      k :: Prime
k = Curve -> Prime
kCurve Curve
e

instance Show Point where
  show :: Point -> String
show Point
Infinity = String
"infinity"
  show (Point Prime
x Prime
y) = String
"(" String -> ShowS
forall a. [a] -> [a] -> [a]
++ Prime -> String
forall a. Show a => a -> String
show Prime
x String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
"," String -> ShowS
forall a. [a] -> [a] -> [a]
++ Prime -> String
forall a. Show a => a -> String
show Prime
y String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
")"

rhs :: Curve -> Gfpx
rhs :: Curve -> Gfpx
rhs Curve
e = [Prime] -> Gfpx
Gfpx.fromCoeff [Curve -> Prime
bCurve Curve
e, Curve -> Prime
aCurve Curve
e, Prime
0, Prime
1]

rhsEvaluate :: Curve -> Gfp -> Gfp
rhsEvaluate :: Curve -> Prime -> Prime
rhsEvaluate Curve
e = Prime -> Gfpx -> Prime -> Prime
Gfpx.evaluate (Curve -> Prime
kCurve Curve
e) (Curve -> Gfpx
rhs Curve
e)

-------------------------------------------------------------------------------
-- Points on the curve
-------------------------------------------------------------------------------

onCurve :: Curve -> Point -> Bool
onCurve :: Curve -> Point -> Bool
onCurve Curve
_ Point
Infinity = Bool
True
onCurve Curve
e (Point Prime
x Prime
y) = Prime -> Prime -> Prime
Prime.square (Curve -> Prime
kCurve Curve
e) Prime
y Prime -> Prime -> Bool
forall a. Eq a => a -> a -> Bool
== Curve -> Prime -> Prime
rhsEvaluate Curve
e Prime
x

xPoints :: Curve -> Gfp -> [Point]
xPoints :: Curve -> Prime -> [Point]
xPoints Curve
e Prime
x =
    case Prime -> Prime -> Residue
jacobiSymbol Prime
y2 Prime
k of
      Residue
NonResidue -> []
      Residue
ZeroResidue -> [Prime -> Prime -> Point
Point Prime
x Prime
0]
      Residue
Residue -> [Prime -> Prime -> Point
Point Prime
x Prime
y, Prime -> Prime -> Point
Point Prime
x Prime
y']
  where
    y2 :: Prime
y2 = Curve -> Prime -> Prime
rhsEvaluate Curve
e Prime
x
    y :: Prime
y = Prime -> Prime -> Prime
Prime.sqrt Prime
k Prime
y2
    y' :: Prime
y' = Prime -> Prime -> Prime
Prime.negate Prime
k Prime
y
    k :: Prime
k = Curve -> Prime
kCurve Curve
e

points :: Curve -> [Point]
points :: Curve -> [Point]
points Curve
e = Point
Infinity Point -> [Point] -> [Point]
forall a. a -> [a] -> [a]
: (Prime -> [Point]) -> [Prime] -> [Point]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap (Curve -> Prime -> [Point]
xPoints Curve
e) (Prime -> [Prime]
Prime.elements (Curve -> Prime
kCurve Curve
e))

-------------------------------------------------------------------------------
-- Discriminant
-------------------------------------------------------------------------------

discriminant :: Curve -> Gfp
discriminant :: Curve -> Prime
discriminant (Curve Prime
k Prime
a Prime
b) =
    Prime -> Prime -> Prime -> Prime
Prime.multiply Prime
k (Prime -> Prime -> Prime
Prime.fromInteger Prime
k (-Prime
16)) Prime
s
  where
    s :: Prime
s = Prime -> Prime -> Prime -> Prime
Prime.add Prime
k Prime
s1 Prime
s2
    s1 :: Prime
s1 = Prime -> Prime -> Prime -> Prime
Prime.multiply Prime
k (Prime -> Prime -> Prime
Prime.fromInteger Prime
k Prime
4) (Prime -> Prime -> Prime
Prime.cube Prime
k Prime
a)
    s2 :: Prime
s2 = Prime -> Prime -> Prime -> Prime
Prime.multiply Prime
k (Prime -> Prime -> Prime
Prime.fromInteger Prime
k Prime
27) (Prime -> Prime -> Prime
Prime.square Prime
k Prime
b)

singular :: Curve -> Bool
singular :: Curve -> Bool
singular = Prime -> Prime -> Bool
forall a. Eq a => a -> a -> Bool
(==) Prime
0 (Prime -> Bool) -> (Curve -> Prime) -> Curve -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Curve -> Prime
discriminant

-------------------------------------------------------------------------------
-- Generating a random elliptic curve and (finite) point on the curve
--
-- https://en.wikipedia.org/wiki/Elliptic_curve_primality
-------------------------------------------------------------------------------

uniformCurve :: RandomGen r => Prime -> r -> ((Curve,Point),r)
uniformCurve :: Prime -> r -> ((Curve, Point), r)
uniformCurve Prime
k | Prime
k Prime -> Prime -> Bool
forall a. Ord a => a -> a -> Bool
<= Prime
3 = String -> r -> ((Curve, Point), r)
forall a. HasCallStack => String -> a
error String
"fields cannot have characteristic 2 or 3"
uniformCurve Prime
k = r -> ((Curve, Point), r)
forall b. RandomGen b => b -> ((Curve, Point), b)
pick
  where
    pick :: b -> ((Curve, Point), b)
pick b
r0 = if Curve -> Bool
singular Curve
e then b -> ((Curve, Point), b)
pick b
r3 else ((Curve
e, Prime -> Prime -> Point
Point Prime
x Prime
y), b
r3)
      where
        (Prime
a,b
r1) = Prime -> b -> (Prime, b)
forall r. RandomGen r => Prime -> r -> (Prime, r)
Prime.uniform Prime
k b
r0
        (Prime
x,b
r2) = Prime -> b -> (Prime, b)
forall r. RandomGen r => Prime -> r -> (Prime, r)
Prime.uniform Prime
k b
r1
        (Prime
y,b
r3) = Prime -> b -> (Prime, b)
forall r. RandomGen r => Prime -> r -> (Prime, r)
Prime.uniform Prime
k b
r2
        x2 :: Prime
x2 = Prime -> Prime -> Prime
Prime.square Prime
k Prime
x
        y2 :: Prime
y2 = Prime -> Prime -> Prime
Prime.square Prime
k Prime
y
        b :: Prime
b = Prime -> Prime -> Prime -> Prime
Prime.subtract Prime
k Prime
y2 (Prime -> Prime -> Prime -> Prime
Prime.multiply Prime
k Prime
x (Prime -> Prime -> Prime -> Prime
Prime.add Prime
k Prime
x2 Prime
a))
        e :: Curve
e = Prime -> Prime -> Prime -> Curve
Curve Prime
k Prime
a Prime
b

uniformPoint :: RandomGen r => Curve -> r -> (Point,r)
uniformPoint :: Curve -> r -> (Point, r)
uniformPoint Curve
e = r -> (Point, r)
forall b. RandomGen b => b -> (Point, b)
pick
  where
    k :: Prime
k = Curve -> Prime
kCurve Curve
e

    pick :: b -> (Point, b)
pick b
r0 =
        case [Point]
ps of
          [] -> b -> (Point, b)
pick b
r1
          [Point
p] -> (Point
p,b
r1)
          [Point
p,Point
p'] -> (if Bool
n then Point
p' else Point
p, b
r2)
          [Point]
_ -> String -> (Point, b)
forall a. HasCallStack => String -> a
error String
"more than 2 points for a fixed x value"
      where
        (Prime
x,b
r1) = Prime -> b -> (Prime, b)
forall r. RandomGen r => Prime -> r -> (Prime, r)
Prime.uniform Prime
k b
r0
        ps :: [Point]
ps = Curve -> Prime -> [Point]
xPoints Curve
e Prime
x
        (Bool
n,b
r2) = b -> (Bool, b)
forall a g. (Random a, RandomGen g) => g -> (a, g)
Random.random b
r1

-------------------------------------------------------------------------------
-- Point negation
--
-- https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication
-------------------------------------------------------------------------------

negate :: Curve -> Point -> Point
negate :: Curve -> Point -> Point
negate Curve
_ Point
Infinity = Point
Infinity
negate (Curve Prime
k Prime
_ Prime
_) (Point Prime
x Prime
y) = Prime -> Prime -> Point
Point Prime
x (Prime -> Prime -> Prime
Prime.negate Prime
k Prime
y)

-------------------------------------------------------------------------------
-- Point addition
--
-- https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication
-------------------------------------------------------------------------------

addLambdaF :: Curve -> Gfp -> Gfp -> Gfp -> Gfp -> Gfp -> Factor Integer Point
addLambdaF :: Curve
-> Prime -> Prime -> Prime -> Prime -> Prime -> Factor Prime Point
addLambdaF Curve
e Prime
n Prime
d Prime
x1 Prime
y1 Prime
x2 = do
    Prime
l <- Prime -> Prime -> Prime -> Factor Prime Prime
Prime.divideF Prime
k Prime
n Prime
d
    let x :: Prime
x = Prime -> Prime -> Prime -> Prime
Prime.subtract Prime
k (Prime -> Prime -> Prime
Prime.square Prime
k Prime
l) (Prime -> Prime -> Prime -> Prime
Prime.add Prime
k Prime
x1 Prime
x2)
    let y :: Prime
y = Prime -> Prime -> Prime -> Prime
Prime.subtract Prime
k (Prime -> Prime -> Prime -> Prime
Prime.multiply Prime
k Prime
l (Prime -> Prime -> Prime -> Prime
Prime.subtract Prime
k Prime
x1 Prime
x)) Prime
y1
    Point -> Factor Prime Point
forall (m :: * -> *) a. Monad m => a -> m a
return (Point -> Factor Prime Point) -> Point -> Factor Prime Point
forall a b. (a -> b) -> a -> b
$ Prime -> Prime -> Point
Point Prime
x Prime
y
  where
    k :: Prime
k = Curve -> Prime
kCurve Curve
e

doubleF :: Curve -> Point -> Factor Integer Point
doubleF :: Curve -> Point -> Factor Prime Point
doubleF Curve
_ Point
Infinity = Point -> Factor Prime Point
forall a b. b -> Either a b
Right Point
Infinity
doubleF Curve
e (Point Prime
x Prime
y) =
    if Prime
y Prime -> Prime -> Bool
forall a. Eq a => a -> a -> Bool
== Prime
0 then Point -> Factor Prime Point
forall a b. b -> Either a b
Right Point
Infinity else Curve
-> Prime -> Prime -> Prime -> Prime -> Prime -> Factor Prime Point
addLambdaF Curve
e Prime
n Prime
d Prime
x Prime
y Prime
x
  where
    n :: Prime
n = Prime -> Prime -> Prime -> Prime
Prime.add Prime
k
          (Prime -> Prime -> Prime -> Prime
Prime.multiply Prime
k (Prime -> Prime -> Prime
Prime.fromInteger Prime
k Prime
3) (Prime -> Prime -> Prime
Prime.square Prime
k Prime
x)) Prime
a
    d :: Prime
d = Prime -> Prime -> Prime -> Prime
Prime.multiply Prime
k (Prime -> Prime -> Prime
Prime.fromInteger Prime
k Prime
2) Prime
y
    k :: Prime
k = Curve -> Prime
kCurve Curve
e
    a :: Prime
a = Curve -> Prime
aCurve Curve
e

double :: Curve -> Point -> Point
double :: Curve -> Point -> Point
double Curve
e Point
p = Factor Prime Point -> Point
forall f a. Show f => Factor f a -> a
runFactor (Factor Prime Point -> Point) -> Factor Prime Point -> Point
forall a b. (a -> b) -> a -> b
$ Curve -> Point -> Factor Prime Point
doubleF Curve
e Point
p

addF :: Curve -> Point -> Point -> Factor Integer Point
addF :: Curve -> Point -> Point -> Factor Prime Point
addF Curve
_ Point
p1 Point
Infinity = Point -> Factor Prime Point
forall a b. b -> Either a b
Right Point
p1
addF Curve
_ Point
Infinity Point
p2 = Point -> Factor Prime Point
forall a b. b -> Either a b
Right Point
p2
addF Curve
e Point
p1 Point
p2 =
    if Prime
x1 Prime -> Prime -> Bool
forall a. Eq a => a -> a -> Bool
/= Prime
x2 then Curve
-> Prime -> Prime -> Prime -> Prime -> Prime -> Factor Prime Point
addLambdaF Curve
e Prime
n Prime
d Prime
x1 Prime
y1 Prime
x2
    else if Prime
y1 Prime -> Prime -> Bool
forall a. Eq a => a -> a -> Bool
== Prime
y2 then Curve -> Point -> Factor Prime Point
doubleF Curve
e Point
p1
    else Point -> Factor Prime Point
forall a b. b -> Either a b
Right Point
Infinity
  where
    n :: Prime
n = Prime -> Prime -> Prime -> Prime
Prime.subtract Prime
k Prime
y2 Prime
y1
    d :: Prime
d = Prime -> Prime -> Prime -> Prime
Prime.subtract Prime
k Prime
x2 Prime
x1
    Point Prime
x1 Prime
y1 = Point
p1
    Point Prime
x2 Prime
y2 = Point
p2
    k :: Prime
k = Curve -> Prime
kCurve Curve
e

add :: Curve -> Point -> Point -> Point
add :: Curve -> Point -> Point -> Point
add Curve
e Point
p1 Point
p2 = Factor Prime Point -> Point
forall f a. Show f => Factor f a -> a
runFactor (Factor Prime Point -> Point) -> Factor Prime Point -> Point
forall a b. (a -> b) -> a -> b
$ Curve -> Point -> Point -> Factor Prime Point
addF Curve
e Point
p1 Point
p2

-------------------------------------------------------------------------------
-- Point multiplication
--
-- https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication
-------------------------------------------------------------------------------

addMultiplyF :: Curve -> Point -> Point -> Integer -> Factor Integer Point
addMultiplyF :: Curve -> Point -> Point -> Prime -> Factor Prime Point
addMultiplyF Curve
_ Point
z Point
_ Prime
0 = Point -> Factor Prime Point
forall a b. b -> Either a b
Right Point
z
addMultiplyF Curve
e Point
z Point
p Prime
n | Prime
n Prime -> Prime -> Bool
forall a. Ord a => a -> a -> Bool
< Prime
0 = Curve -> Point -> Point -> Prime -> Factor Prime Point
addMultiplyF Curve
e Point
z (Curve -> Point -> Point
Factor.Ec.negate Curve
e Point
p) (-Prime
n)
addMultiplyF Curve
_ Point
z Point
Infinity Prime
_ = Point -> Factor Prime Point
forall a b. b -> Either a b
Right Point
z
addMultiplyF Curve
e Point
z Point
p Prime
n = do
    Point
z' <- if Prime -> Bool
forall a. Integral a => a -> Bool
even Prime
n then Point -> Factor Prime Point
forall (m :: * -> *) a. Monad m => a -> m a
return Point
z else Curve -> Point -> Point -> Factor Prime Point
addF Curve
e Point
z Point
p
    Point
p' <- Curve -> Point -> Factor Prime Point
doubleF Curve
e Point
p
    Curve -> Point -> Point -> Prime -> Factor Prime Point
addMultiplyF Curve
e Point
z' Point
p' Prime
n'
  where
    n' :: Prime
n' = Prime
n Prime -> Prime -> Prime
forall a. Integral a => a -> a -> a
`div` Prime
2

addMultiply :: Curve -> Point -> Point -> Integer -> Point
addMultiply :: Curve -> Point -> Point -> Prime -> Point
addMultiply Curve
e Point
z Point
p Prime
n = Factor Prime Point -> Point
forall f a. Show f => Factor f a -> a
runFactor (Factor Prime Point -> Point) -> Factor Prime Point -> Point
forall a b. (a -> b) -> a -> b
$ Curve -> Point -> Point -> Prime -> Factor Prime Point
addMultiplyF Curve
e Point
z Point
p Prime
n

multiplyF :: Curve -> Point -> Integer -> Factor Integer Point
multiplyF :: Curve -> Point -> Prime -> Factor Prime Point
multiplyF Curve
e = Curve -> Point -> Point -> Prime -> Factor Prime Point
addMultiplyF Curve
e Point
Infinity

multiply :: Curve -> Point -> Integer -> Point
multiply :: Curve -> Point -> Prime -> Point
multiply Curve
e Point
p Prime
n = Factor Prime Point -> Point
forall f a. Show f => Factor f a -> a
runFactor (Factor Prime Point -> Point) -> Factor Prime Point -> Point
forall a b. (a -> b) -> a -> b
$ Curve -> Point -> Prime -> Factor Prime Point
multiplyF Curve
e Point
p Prime
n

-------------------------------------------------------------------------------
-- Lenstra's elliptic curve method (ECM) factorization algorithm
--
-- Input: An integer greater than 1 that is not divisible by 2 or 3
-- Output: Either a nontrivial factor of the input or failure
--
-- https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization
-------------------------------------------------------------------------------

data TargetConfig =
    CurvePointTargetConfig Int
  | PrimeTargetConfig Int
  deriving (TargetConfig -> TargetConfig -> Bool
(TargetConfig -> TargetConfig -> Bool)
-> (TargetConfig -> TargetConfig -> Bool) -> Eq TargetConfig
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: TargetConfig -> TargetConfig -> Bool
$c/= :: TargetConfig -> TargetConfig -> Bool
== :: TargetConfig -> TargetConfig -> Bool
$c== :: TargetConfig -> TargetConfig -> Bool
Eq,Eq TargetConfig
Eq TargetConfig
-> (TargetConfig -> TargetConfig -> Ordering)
-> (TargetConfig -> TargetConfig -> Bool)
-> (TargetConfig -> TargetConfig -> Bool)
-> (TargetConfig -> TargetConfig -> Bool)
-> (TargetConfig -> TargetConfig -> Bool)
-> (TargetConfig -> TargetConfig -> TargetConfig)
-> (TargetConfig -> TargetConfig -> TargetConfig)
-> Ord TargetConfig
TargetConfig -> TargetConfig -> Bool
TargetConfig -> TargetConfig -> Ordering
TargetConfig -> TargetConfig -> TargetConfig
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: TargetConfig -> TargetConfig -> TargetConfig
$cmin :: TargetConfig -> TargetConfig -> TargetConfig
max :: TargetConfig -> TargetConfig -> TargetConfig
$cmax :: TargetConfig -> TargetConfig -> TargetConfig
>= :: TargetConfig -> TargetConfig -> Bool
$c>= :: TargetConfig -> TargetConfig -> Bool
> :: TargetConfig -> TargetConfig -> Bool
$c> :: TargetConfig -> TargetConfig -> Bool
<= :: TargetConfig -> TargetConfig -> Bool
$c<= :: TargetConfig -> TargetConfig -> Bool
< :: TargetConfig -> TargetConfig -> Bool
$c< :: TargetConfig -> TargetConfig -> Bool
compare :: TargetConfig -> TargetConfig -> Ordering
$ccompare :: TargetConfig -> TargetConfig -> Ordering
$cp1Ord :: Eq TargetConfig
Ord,Int -> TargetConfig -> ShowS
[TargetConfig] -> ShowS
TargetConfig -> String
(Int -> TargetConfig -> ShowS)
-> (TargetConfig -> String)
-> ([TargetConfig] -> ShowS)
-> Show TargetConfig
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [TargetConfig] -> ShowS
$cshowList :: [TargetConfig] -> ShowS
show :: TargetConfig -> String
$cshow :: TargetConfig -> String
showsPrec :: Int -> TargetConfig -> ShowS
$cshowsPrec :: Int -> TargetConfig -> ShowS
Show)

data Config =
    Config {Config -> [TargetConfig]
targetConfig :: [TargetConfig]}
  deriving (Config -> Config -> Bool
(Config -> Config -> Bool)
-> (Config -> Config -> Bool) -> Eq Config
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Config -> Config -> Bool
$c/= :: Config -> Config -> Bool
== :: Config -> Config -> Bool
$c== :: Config -> Config -> Bool
Eq,Eq Config
Eq Config
-> (Config -> Config -> Ordering)
-> (Config -> Config -> Bool)
-> (Config -> Config -> Bool)
-> (Config -> Config -> Bool)
-> (Config -> Config -> Bool)
-> (Config -> Config -> Config)
-> (Config -> Config -> Config)
-> Ord Config
Config -> Config -> Bool
Config -> Config -> Ordering
Config -> Config -> Config
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: Config -> Config -> Config
$cmin :: Config -> Config -> Config
max :: Config -> Config -> Config
$cmax :: Config -> Config -> Config
>= :: Config -> Config -> Bool
$c>= :: Config -> Config -> Bool
> :: Config -> Config -> Bool
$c> :: Config -> Config -> Bool
<= :: Config -> Config -> Bool
$c<= :: Config -> Config -> Bool
< :: Config -> Config -> Bool
$c< :: Config -> Config -> Bool
compare :: Config -> Config -> Ordering
$ccompare :: Config -> Config -> Ordering
$cp1Ord :: Eq Config
Ord,Int -> Config -> ShowS
[Config] -> ShowS
Config -> String
(Int -> Config -> ShowS)
-> (Config -> String) -> ([Config] -> ShowS) -> Show Config
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Config] -> ShowS
$cshowList :: [Config] -> ShowS
show :: Config -> String
$cshow :: Config -> String
showsPrec :: Int -> Config -> ShowS
$cshowsPrec :: Int -> Config -> ShowS
Show)

defaultConfig :: Config
defaultConfig :: Config
defaultConfig =
    Config :: [TargetConfig] -> Config
Config {targetConfig :: [TargetConfig]
targetConfig = Int -> Int -> [TargetConfig]
targets Int
10 Int
30}
  where
    targets :: Int -> Int -> [TargetConfig]
targets Int
c Int
p | Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Int
c Int
p Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
1 = []
    targets Int
c Int
p =
      if Int -> Prime
forall a. Integral a => a -> Prime
toInteger Int
c Prime -> Prime -> Prime
forall a b. (Num a, Integral b) => a -> b -> a
^ (Prime
3 :: Integer) Prime -> Prime -> Bool
forall a. Ord a => a -> a -> Bool
< Int -> Prime
forall a. Integral a => a -> Prime
toInteger Int
p Prime -> Prime -> Prime
forall a b. (Num a, Integral b) => a -> b -> a
^ (Prime
2 :: Integer) then
        Int -> TargetConfig
CurvePointTargetConfig Int
c TargetConfig -> [TargetConfig] -> [TargetConfig]
forall a. a -> [a] -> [a]
: Int -> Int -> [TargetConfig]
targets (Int
c Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
c Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
3) Int
p
      else
        Int -> TargetConfig
PrimeTargetConfig Int
p TargetConfig -> [TargetConfig] -> [TargetConfig]
forall a. a -> [a] -> [a]
: Int -> Int -> [TargetConfig]
targets Int
c (Int
p Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
p Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
3)

limitPrimesConfig :: Maybe Int -> Config -> Config
limitPrimesConfig :: Maybe Int -> Config -> Config
limitPrimesConfig Maybe Int
Nothing Config
cfg = Config
cfg
limitPrimesConfig (Just Int
q) Config
cfg =
    Config
cfg {targetConfig :: [TargetConfig]
targetConfig = (TargetConfig -> Bool) -> [TargetConfig] -> [TargetConfig]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile TargetConfig -> Bool
within (Config -> [TargetConfig]
targetConfig Config
cfg)}
  where
    within :: TargetConfig -> Bool
within (PrimeTargetConfig Int
qt) = Int
qt Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
q
    within TargetConfig
_ = Bool
True

factorPrime :: [(Curve,Point)] -> Prime -> Factor Integer [(Curve,Point)]
factorPrime :: [(Curve, Point)] -> Prime -> Factor Prime [(Curve, Point)]
factorPrime [] Prime
_ = [(Curve, Point)] -> Factor Prime [(Curve, Point)]
forall (m :: * -> *) a. Monad m => a -> m a
return []
factorPrime [(Curve, Point)]
eps Prime
q = ((Curve, Point) -> Bool) -> [(Curve, Point)] -> [(Curve, Point)]
forall a. (a -> Bool) -> [a] -> [a]
filter (Curve, Point) -> Bool
forall a. (a, Point) -> Bool
fin ([(Curve, Point)] -> [(Curve, Point)])
-> Factor Prime [(Curve, Point)] -> Factor Prime [(Curve, Point)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ((Curve, Point) -> Either Prime (Curve, Point))
-> [(Curve, Point)] -> Factor Prime [(Curve, Point)]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM (Curve, Point) -> Either Prime (Curve, Point)
fac [(Curve, Point)]
eps
  where
    fac :: (Curve, Point) -> Either Prime (Curve, Point)
fac (Curve
e,Point
p) = ((,) Curve
e) (Point -> (Curve, Point))
-> Factor Prime Point -> Either Prime (Curve, Point)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Curve -> Point -> Prime -> Factor Prime Point
multiplyF Curve
e Point
p Prime
n
    fin :: (a, Point) -> Bool
fin (a
_,Point
p) = Point
p Point -> Point -> Bool
forall a. Eq a => a -> a -> Bool
/= Point
Infinity
    n :: Prime
n = [Prime] -> Prime
forall a. [a] -> a
last ([Prime] -> Prime) -> [Prime] -> Prime
forall a b. (a -> b) -> a -> b
$ (Prime -> Bool) -> [Prime] -> [Prime]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile (\Prime
i -> Prime
i Prime -> Prime -> Bool
forall a. Ord a => a -> a -> Bool
< Prime
k) ([Prime] -> [Prime]) -> [Prime] -> [Prime]
forall a b. (a -> b) -> a -> b
$ (Prime -> Prime) -> Prime -> [Prime]
forall a. (a -> a) -> a -> [a]
iterate (Prime -> Prime -> Prime
forall a. Num a => a -> a -> a
(*) Prime
q) Prime
1
    k :: Prime
k = Curve -> Prime
kCurve (Curve -> Prime) -> Curve -> Prime
forall a b. (a -> b) -> a -> b
$ (Curve, Point) -> Curve
forall a b. (a, b) -> a
fst ((Curve, Point) -> Curve) -> (Curve, Point) -> Curve
forall a b. (a -> b) -> a -> b
$ [(Curve, Point)] -> (Curve, Point)
forall a. [a] -> a
head [(Curve, Point)]
eps

factorPrimes :: [(Curve,Point)] -> [Prime] -> Factor Integer [(Curve,Point)]
factorPrimes :: [(Curve, Point)] -> [Prime] -> Factor Prime [(Curve, Point)]
factorPrimes [] [Prime]
_ = [(Curve, Point)] -> Factor Prime [(Curve, Point)]
forall (m :: * -> *) a. Monad m => a -> m a
return []
factorPrimes [(Curve, Point)]
ep [] = [(Curve, Point)] -> Factor Prime [(Curve, Point)]
forall (m :: * -> *) a. Monad m => a -> m a
return [(Curve, Point)]
ep
factorPrimes [(Curve, Point)]
ep (Prime
q : [Prime]
qs) = [(Curve, Point)] -> Prime -> Factor Prime [(Curve, Point)]
factorPrime [(Curve, Point)]
ep Prime
q Factor Prime [(Curve, Point)]
-> ([(Curve, Point)] -> Factor Prime [(Curve, Point)])
-> Factor Prime [(Curve, Point)]
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= ([(Curve, Point)] -> [Prime] -> Factor Prime [(Curve, Point)])
-> [Prime] -> [(Curve, Point)] -> Factor Prime [(Curve, Point)]
forall a b c. (a -> b -> c) -> b -> a -> c
flip [(Curve, Point)] -> [Prime] -> Factor Prime [(Curve, Point)]
factorPrimes [Prime]
qs

factorTargets ::
    RandomGen r => Integer -> ([(Curve,Point)],Int) -> [TargetConfig] -> r ->
    Verbose (Maybe Integer, r)
factorTargets :: Prime
-> ([(Curve, Point)], Int)
-> [TargetConfig]
-> r
-> Verbose (Maybe Prime, r)
factorTargets Prime
_ ([(Curve, Point)], Int)
_ [] r
r = do
    String -> Verbose ()
comment String
"No more ECM curve point/prime targets, factorization failed"
    (Maybe Prime, r) -> Verbose (Maybe Prime, r)
forall (m :: * -> *) a. Monad m => a -> m a
return (Maybe Prime
forall a. Maybe a
Nothing,r
r)
factorTargets Prime
k ([(Curve, Point)]
ep,Int
q) (CurvePointTargetConfig Int
ept : [TargetConfig]
ts) r
r = do
    Int
epn <- Int -> Verbose Int
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int -> Verbose Int) -> Int -> Verbose Int
forall a b. (a -> b) -> a -> b
$ [(Curve, Point)] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [(Curve, Point)]
ep
    String -> Verbose ()
comment (String -> Verbose ()) -> String -> Verbose ()
forall a b. (a -> b) -> a -> b
$ String
"Current number of curve points is " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
epn
    case Int
ept Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
epn of
      Int
epx | Int
epx Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0 -> do
        String -> Verbose ()
comment (String -> Verbose ()) -> String -> Verbose ()
forall a b. (a -> b) -> a -> b
$ String
"Generating " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
epx String -> ShowS
forall a. [a] -> [a] -> [a]
++
                  String
" new curve points to achieve target of " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
ept
        ([(Curve, Point)]
ep0,r
r') <- ([(Curve, Point)], r) -> Verbose ([(Curve, Point)], r)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (([(Curve, Point)], r) -> Verbose ([(Curve, Point)], r))
-> ([(Curve, Point)], r) -> Verbose ([(Curve, Point)], r)
forall a b. (a -> b) -> a -> b
$ (r -> ((Curve, Point), r)) -> Int -> r -> ([(Curve, Point)], r)
forall b a. (b -> (a, b)) -> Int -> b -> ([a], b)
unfoldrN (Prime -> r -> ((Curve, Point), r)
forall r. RandomGen r => Prime -> r -> ((Curve, Point), r)
uniformCurve Prime
k) Int
epx r
r
        if Int
q Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 then Prime
-> ([(Curve, Point)], Int)
-> [TargetConfig]
-> r
-> Verbose (Maybe Prime, r)
forall r.
RandomGen r =>
Prime
-> ([(Curve, Point)], Int)
-> [TargetConfig]
-> r
-> Verbose (Maybe Prime, r)
factorTargets Prime
k ([(Curve, Point)]
ep [(Curve, Point)] -> [(Curve, Point)] -> [(Curve, Point)]
forall a. [a] -> [a] -> [a]
++ [(Curve, Point)]
ep0, Int
q) [TargetConfig]
ts r
r' else do
          String -> Verbose ()
comment (String -> Verbose ()) -> String -> Verbose ()
forall a b. (a -> b) -> a -> b
$ String
"Multiplying new curve points by first " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
q String -> ShowS
forall a. [a] -> [a] -> [a]
++
                    String
" primes"
          Factor Prime [(Curve, Point)]
f <- Factor Prime [(Curve, Point)]
-> Verbose (Factor Prime [(Curve, Point)])
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Factor Prime [(Curve, Point)]
 -> Verbose (Factor Prime [(Curve, Point)]))
-> Factor Prime [(Curve, Point)]
-> Verbose (Factor Prime [(Curve, Point)])
forall a b. (a -> b) -> a -> b
$ [(Curve, Point)] -> [Prime] -> Factor Prime [(Curve, Point)]
factorPrimes [(Curve, Point)]
ep0 (Int -> [Prime] -> [Prime]
forall a. Int -> [a] -> [a]
take Int
q [Prime]
Prime.primes)
          case Factor Prime [(Curve, Point)]
f of
            Left Prime
g -> (Maybe Prime, r) -> Verbose (Maybe Prime, r)
forall (m :: * -> *) a. Monad m => a -> m a
return (Prime -> Maybe Prime
forall a. a -> Maybe a
Just Prime
g, r
r')
            Right [(Curve, Point)]
ep' -> Prime
-> ([(Curve, Point)], Int)
-> [TargetConfig]
-> r
-> Verbose (Maybe Prime, r)
forall r.
RandomGen r =>
Prime
-> ([(Curve, Point)], Int)
-> [TargetConfig]
-> r
-> Verbose (Maybe Prime, r)
factorTargets Prime
k ([(Curve, Point)]
ep [(Curve, Point)] -> [(Curve, Point)] -> [(Curve, Point)]
forall a. [a] -> [a] -> [a]
++ [(Curve, Point)]
ep', Int
q) [TargetConfig]
ts r
r'
      Int
_ -> do
        String -> Verbose ()
comment (String -> Verbose ()) -> String -> Verbose ()
forall a b. (a -> b) -> a -> b
$ String
"Curve point target of " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
ept String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" already achieved"
        Prime
-> ([(Curve, Point)], Int)
-> [TargetConfig]
-> r
-> Verbose (Maybe Prime, r)
forall r.
RandomGen r =>
Prime
-> ([(Curve, Point)], Int)
-> [TargetConfig]
-> r
-> Verbose (Maybe Prime, r)
factorTargets Prime
k ([(Curve, Point)]
ep,Int
q) [TargetConfig]
ts r
r
factorTargets Prime
k ([(Curve, Point)]
ep,Int
q) (PrimeTargetConfig Int
qt : [TargetConfig]
ts) r
r = do
    if [(Curve, Point)] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [(Curve, Point)]
ep then () -> Verbose ()
forall (m :: * -> *) a. Monad m => a -> m a
return () else String -> Verbose ()
comment (String -> Verbose ()) -> String -> Verbose ()
forall a b. (a -> b) -> a -> b
$
      String
"Already multiplied " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show ([(Curve, Point)] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [(Curve, Point)]
ep) String -> ShowS
forall a. [a] -> [a] -> [a]
++
      String
" curve points by first " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
q String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" primes"
    case Int
qt Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
q of
      Int
qx | Int
qx Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0 -> do
        String -> Verbose ()
comment (String -> Verbose ()) -> String -> Verbose ()
forall a b. (a -> b) -> a -> b
$ (if [(Curve, Point)] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [(Curve, Point)]
ep then
                     (if Int
q Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 then String
"Setting" else String
"Raising") String -> ShowS
forall a. [a] -> [a] -> [a]
++
                     String
" initial prime target to "
                   else
                     String
"Multiplying by next " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
qx String -> ShowS
forall a. [a] -> [a] -> [a]
++
                     String
" primes to achieve target of ") String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
qt
        Factor Prime [(Curve, Point)]
f <- Factor Prime [(Curve, Point)]
-> Verbose (Factor Prime [(Curve, Point)])
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Factor Prime [(Curve, Point)]
 -> Verbose (Factor Prime [(Curve, Point)]))
-> Factor Prime [(Curve, Point)]
-> Verbose (Factor Prime [(Curve, Point)])
forall a b. (a -> b) -> a -> b
$ [(Curve, Point)] -> [Prime] -> Factor Prime [(Curve, Point)]
factorPrimes [(Curve, Point)]
ep (Int -> [Prime] -> [Prime]
forall a. Int -> [a] -> [a]
take Int
qx (Int -> [Prime] -> [Prime]
forall a. Int -> [a] -> [a]
drop Int
q [Prime]
Prime.primes))
        case Factor Prime [(Curve, Point)]
f of
          Left Prime
g -> (Maybe Prime, r) -> Verbose (Maybe Prime, r)
forall (m :: * -> *) a. Monad m => a -> m a
return (Prime -> Maybe Prime
forall a. a -> Maybe a
Just Prime
g, r
r)
          Right [(Curve, Point)]
ep' -> Prime
-> ([(Curve, Point)], Int)
-> [TargetConfig]
-> r
-> Verbose (Maybe Prime, r)
forall r.
RandomGen r =>
Prime
-> ([(Curve, Point)], Int)
-> [TargetConfig]
-> r
-> Verbose (Maybe Prime, r)
factorTargets Prime
k ([(Curve, Point)]
ep',Int
qt) [TargetConfig]
ts r
r
      Int
_ -> do
        String -> Verbose ()
comment (String -> Verbose ()) -> String -> Verbose ()
forall a b. (a -> b) -> a -> b
$ String
"Prime target of " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
qt String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" already achieved"
        Prime
-> ([(Curve, Point)], Int)
-> [TargetConfig]
-> r
-> Verbose (Maybe Prime, r)
forall r.
RandomGen r =>
Prime
-> ([(Curve, Point)], Int)
-> [TargetConfig]
-> r
-> Verbose (Maybe Prime, r)
factorTargets Prime
k ([(Curve, Point)]
ep,Int
q) [TargetConfig]
ts r
r

factor :: RandomGen r => Config -> Integer -> r -> Verbose (Maybe Integer, r)
factor :: Config -> Prime -> r -> Verbose (Maybe Prime, r)
factor Config
cfg Prime
k r
r = do
    --comment $ "ECM configuration = " ++ show cfg
    Prime
-> ([(Curve, Point)], Int)
-> [TargetConfig]
-> r
-> Verbose (Maybe Prime, r)
forall r.
RandomGen r =>
Prime
-> ([(Curve, Point)], Int)
-> [TargetConfig]
-> r
-> Verbose (Maybe Prime, r)
factorTargets Prime
k ([],Int
0) (Config -> [TargetConfig]
targetConfig Config
cfg) r
r

-------------------------------------------------------------------------------
-- Division polynomials
--
-- https://en.wikipedia.org/wiki/Division_polynomials
-- https://math.mit.edu/classes/18.783/2019/LectureNotes6.pdf
-------------------------------------------------------------------------------

data DivisionPolynomial =
    DivisionPolynomial
      {DivisionPolynomial -> Gfpx
psiDivisionPolynomial :: Gfpx,    -- if n is even multiply psi_n by 2y
       DivisionPolynomial -> Gfpx
phiDivisionPolynomial :: Gfpx,
       DivisionPolynomial -> Gfpx
omegaDivisionPolynomial :: Gfpx}  -- if n is odd multiply omega_n by y
  deriving (DivisionPolynomial -> DivisionPolynomial -> Bool
(DivisionPolynomial -> DivisionPolynomial -> Bool)
-> (DivisionPolynomial -> DivisionPolynomial -> Bool)
-> Eq DivisionPolynomial
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: DivisionPolynomial -> DivisionPolynomial -> Bool
$c/= :: DivisionPolynomial -> DivisionPolynomial -> Bool
== :: DivisionPolynomial -> DivisionPolynomial -> Bool
$c== :: DivisionPolynomial -> DivisionPolynomial -> Bool
Eq,Eq DivisionPolynomial
Eq DivisionPolynomial
-> (DivisionPolynomial -> DivisionPolynomial -> Ordering)
-> (DivisionPolynomial -> DivisionPolynomial -> Bool)
-> (DivisionPolynomial -> DivisionPolynomial -> Bool)
-> (DivisionPolynomial -> DivisionPolynomial -> Bool)
-> (DivisionPolynomial -> DivisionPolynomial -> Bool)
-> (DivisionPolynomial -> DivisionPolynomial -> DivisionPolynomial)
-> (DivisionPolynomial -> DivisionPolynomial -> DivisionPolynomial)
-> Ord DivisionPolynomial
DivisionPolynomial -> DivisionPolynomial -> Bool
DivisionPolynomial -> DivisionPolynomial -> Ordering
DivisionPolynomial -> DivisionPolynomial -> DivisionPolynomial
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: DivisionPolynomial -> DivisionPolynomial -> DivisionPolynomial
$cmin :: DivisionPolynomial -> DivisionPolynomial -> DivisionPolynomial
max :: DivisionPolynomial -> DivisionPolynomial -> DivisionPolynomial
$cmax :: DivisionPolynomial -> DivisionPolynomial -> DivisionPolynomial
>= :: DivisionPolynomial -> DivisionPolynomial -> Bool
$c>= :: DivisionPolynomial -> DivisionPolynomial -> Bool
> :: DivisionPolynomial -> DivisionPolynomial -> Bool
$c> :: DivisionPolynomial -> DivisionPolynomial -> Bool
<= :: DivisionPolynomial -> DivisionPolynomial -> Bool
$c<= :: DivisionPolynomial -> DivisionPolynomial -> Bool
< :: DivisionPolynomial -> DivisionPolynomial -> Bool
$c< :: DivisionPolynomial -> DivisionPolynomial -> Bool
compare :: DivisionPolynomial -> DivisionPolynomial -> Ordering
$ccompare :: DivisionPolynomial -> DivisionPolynomial -> Ordering
$cp1Ord :: Eq DivisionPolynomial
Ord,Int -> DivisionPolynomial -> ShowS
[DivisionPolynomial] -> ShowS
DivisionPolynomial -> String
(Int -> DivisionPolynomial -> ShowS)
-> (DivisionPolynomial -> String)
-> ([DivisionPolynomial] -> ShowS)
-> Show DivisionPolynomial
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [DivisionPolynomial] -> ShowS
$cshowList :: [DivisionPolynomial] -> ShowS
show :: DivisionPolynomial -> String
$cshow :: DivisionPolynomial -> String
showsPrec :: Int -> DivisionPolynomial -> ShowS
$cshowsPrec :: Int -> DivisionPolynomial -> ShowS
Show)

psiDivisionPolynomials :: Curve -> [Gfpx]
psiDivisionPolynomials :: Curve -> [Gfpx]
psiDivisionPolynomials Curve
e = Gfpx
p_0 Gfpx -> [Gfpx] -> [Gfpx]
forall a. a -> [a] -> [a]
: Bool -> Gfpx -> Gfpx -> Gfpx -> Gfpx -> [Gfpx] -> [Gfpx]
p_2n_1 Bool
True Gfpx
p_1 Gfpx
p_2 Gfpx
p_3 Gfpx
p_4 []
  where
    p_0 :: Gfpx
p_0 = Gfpx
Gfpx.zero
    p_1 :: Gfpx
p_1 = Gfpx
Gfpx.one
    p_2 :: Gfpx
p_2 = Gfpx
Gfpx.one
    p_3 :: Gfpx
p_3 = [Prime] -> Gfpx
Gfpx.fromCoeff
            [Prime -> Prime -> Prime
Prime.negate Prime
k (Prime -> Prime -> Prime
Prime.square Prime
k Prime
a),
             Prime -> Prime -> Prime -> Prime
Prime.multiply Prime
k (Prime -> Prime -> Prime
Prime.fromInteger Prime
k Prime
12) Prime
b,
             Prime -> Prime -> Prime -> Prime
Prime.multiply Prime
k (Prime -> Prime -> Prime
Prime.fromInteger Prime
k Prime
6) Prime
a,
             Prime
0,
             Prime -> Prime -> Prime
Prime.fromInteger Prime
k Prime
3]
    p_4 :: Gfpx
p_4 = [Prime] -> Gfpx
Gfpx.fromCoeff
            [Prime -> Prime -> Prime -> Prime
Prime.subtract Prime
k
               (Prime -> Prime -> Prime -> Prime
Prime.multiply Prime
k (Prime -> Prime -> Prime
Prime.fromInteger Prime
k (-Prime
2)) (Prime -> Prime -> Prime
Prime.cube Prime
k Prime
a))
               (Prime -> Prime -> Prime -> Prime
Prime.multiply Prime
k (Prime -> Prime -> Prime
Prime.fromInteger Prime
k Prime
16) (Prime -> Prime -> Prime
Prime.square Prime
k Prime
b)),
             Prime -> Prime -> Prime -> Prime
Prime.multiply Prime
k (Prime -> Prime -> Prime
Prime.fromInteger Prime
k (-Prime
8)) (Prime -> Prime -> Prime -> Prime
Prime.multiply Prime
k Prime
a Prime
b),
             Prime -> Prime -> Prime -> Prime
Prime.multiply Prime
k (Prime -> Prime -> Prime
Prime.fromInteger Prime
k (-Prime
10)) (Prime -> Prime -> Prime
Prime.square Prime
k Prime
a),
             Prime -> Prime -> Prime -> Prime
Prime.multiply Prime
k (Prime -> Prime -> Prime
Prime.fromInteger Prime
k Prime
40) Prime
b,
             Prime -> Prime -> Prime -> Prime
Prime.multiply Prime
k (Prime -> Prime -> Prime
Prime.fromInteger Prime
k Prime
10) Prime
a,
             Prime
0,
             Prime -> Prime -> Prime
Prime.fromInteger Prime
k Prime
2]

    p_2n_1 :: Bool -> Gfpx -> Gfpx -> Gfpx -> Gfpx -> [Gfpx] -> [Gfpx]
p_2n_1 Bool
nEven Gfpx
p_n_m1 Gfpx
p_n Gfpx
p_n_1 Gfpx
p_n_2 [Gfpx]
p_rest =
        Bool -> Gfpx -> Gfpx -> Gfpx -> Gfpx -> Gfpx -> [Gfpx] -> [Gfpx]
p_2n (Bool -> Bool
not Bool
nEven) Gfpx
p_n_m1 Gfpx
p_n Gfpx
p_n_1 Gfpx
p_n_2 Gfpx
p_n_3 [Gfpx]
p_rest'
      where
        (Gfpx
p_n_3,[Gfpx]
p_rest') = case [Gfpx]
p_rest of
                            [] -> (Gfpx
p,[])
                            p_h : p_t -> (Gfpx
p_h, [Gfpx]
p_t [Gfpx] -> [Gfpx] -> [Gfpx]
forall a. [a] -> [a] -> [a]
++ [Gfpx
p])
        p :: Gfpx
p = if Bool
nEven then Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.subtract Prime
k (Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.multiply Prime
k Gfpx
f2 Gfpx
s) Gfpx
t
            else Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.subtract Prime
k Gfpx
s (Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.multiply Prime
k Gfpx
f2 Gfpx
t)
        s :: Gfpx
s = Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.multiply Prime
k Gfpx
p_n_2 (Prime -> Gfpx -> Gfpx
Gfpx.cube Prime
k Gfpx
p_n)
        t :: Gfpx
t = Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.multiply Prime
k Gfpx
p_n_m1 (Prime -> Gfpx -> Gfpx
Gfpx.cube Prime
k Gfpx
p_n_1)

    p_2n :: Bool -> Gfpx -> Gfpx -> Gfpx -> Gfpx -> Gfpx -> [Gfpx] -> [Gfpx]
p_2n Bool
nEven Gfpx
p_n_m2 Gfpx
p_n_m1 Gfpx
p_n Gfpx
p_n_1 Gfpx
p_n_2 [Gfpx]
p_rest =
        Gfpx
p_n_m2 Gfpx -> [Gfpx] -> [Gfpx]
forall a. a -> [a] -> [a]
: Bool -> Gfpx -> Gfpx -> Gfpx -> Gfpx -> [Gfpx] -> [Gfpx]
p_2n_1 Bool
nEven Gfpx
p_n_m1 Gfpx
p_n Gfpx
p_n_1 Gfpx
p_n_2 ([Gfpx]
p_rest [Gfpx] -> [Gfpx] -> [Gfpx]
forall a. [a] -> [a] -> [a]
++ [Gfpx
p])
      where
        p :: Gfpx
p = Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.multiply Prime
k Gfpx
p_n (Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.subtract Prime
k Gfpx
s Gfpx
t)
        s :: Gfpx
s = Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.multiply Prime
k Gfpx
p_n_2 (Prime -> Gfpx -> Gfpx
Gfpx.square Prime
k Gfpx
p_n_m1)
        t :: Gfpx
t = Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.multiply Prime
k Gfpx
p_n_m2 (Prime -> Gfpx -> Gfpx
Gfpx.square Prime
k Gfpx
p_n_1)

    k :: Prime
k = Curve -> Prime
kCurve Curve
e
    a :: Prime
a = Curve -> Prime
aCurve Curve
e
    b :: Prime
b = Curve -> Prime
bCurve Curve
e
    f :: Gfpx
f = Prime -> Prime -> Gfpx -> Gfpx
Gfpx.multiplyConstant Prime
k (Prime -> Prime -> Prime
Prime.fromInteger Prime
k Prime
4) (Curve -> Gfpx
rhs Curve
e)
    f2 :: Gfpx
f2 = Prime -> Gfpx -> Gfpx
Gfpx.square Prime
k Gfpx
f

divisionPolynomials :: Curve -> [DivisionPolynomial]
divisionPolynomials :: Curve -> [DivisionPolynomial]
divisionPolynomials Curve
e =
    case Curve -> [Gfpx]
psiDivisionPolynomials Curve
e of
      Gfpx
p_0 : Gfpx
p_1 : Gfpx
p_2 : [Gfpx]
p_rest ->
        Bool
-> Gfpx -> Gfpx -> Gfpx -> Gfpx -> [Gfpx] -> [DivisionPolynomial]
lift Bool
True (Prime -> Gfpx -> Gfpx
Gfpx.negate Prime
k Gfpx
p_2) (Prime -> Gfpx -> Gfpx
Gfpx.negate Prime
k Gfpx
p_1) Gfpx
p_0 Gfpx
p_1 (Gfpx
p_2 Gfpx -> [Gfpx] -> [Gfpx]
forall a. a -> [a] -> [a]
: [Gfpx]
p_rest)
      [Gfpx]
_ -> String -> [DivisionPolynomial]
forall a. HasCallStack => String -> a
error String
"not enough psi division polynomials"
  where
    lift :: Bool
-> Gfpx -> Gfpx -> Gfpx -> Gfpx -> [Gfpx] -> [DivisionPolynomial]
lift Bool
_ Gfpx
_ Gfpx
_ Gfpx
_ Gfpx
_ [] = String -> [DivisionPolynomial]
forall a. HasCallStack => String -> a
error String
"ran out of psi division polynomials"
    lift Bool
nEven Gfpx
psi_n_m2 Gfpx
psi_n_m1 Gfpx
psi_n Gfpx
psi_n_1 (Gfpx
psi_n_2 : [Gfpx]
psi_rest) =
        DivisionPolynomial
p_n DivisionPolynomial -> [DivisionPolynomial] -> [DivisionPolynomial]
forall a. a -> [a] -> [a]
: Bool
-> Gfpx -> Gfpx -> Gfpx -> Gfpx -> [Gfpx] -> [DivisionPolynomial]
lift (Bool -> Bool
not Bool
nEven) Gfpx
psi_n_m1 Gfpx
psi_n Gfpx
psi_n_1 Gfpx
psi_n_2 [Gfpx]
psi_rest
      where
        p_n :: DivisionPolynomial
p_n = DivisionPolynomial :: Gfpx -> Gfpx -> Gfpx -> DivisionPolynomial
DivisionPolynomial
                {psiDivisionPolynomial :: Gfpx
psiDivisionPolynomial = Gfpx
psi_n,
                 phiDivisionPolynomial :: Gfpx
phiDivisionPolynomial = Gfpx
phi_n,
                 omegaDivisionPolynomial :: Gfpx
omegaDivisionPolynomial = Gfpx
omega_n}

        phi_n :: Gfpx
phi_n = if Bool
nEven then Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.subtract Prime
k (Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.multiply Prime
k Gfpx
f Gfpx
s) Gfpx
t
                else Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.subtract Prime
k Gfpx
s (Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.multiply Prime
k Gfpx
f Gfpx
t)
          where
            s :: Gfpx
s = Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.multiply Prime
k Gfpx
Gfpx.variable (Prime -> Gfpx -> Gfpx
Gfpx.square Prime
k Gfpx
psi_n)
            t :: Gfpx
t = Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.multiply Prime
k Gfpx
psi_n_1 Gfpx
psi_n_m1

        omega_n :: Gfpx
omega_n = if Bool
nEven then Prime -> Prime -> Gfpx -> Gfpx
Gfpx.multiplyConstant Prime
k Prime
h Gfpx
p else Gfpx
p
          where
            p :: Gfpx
p = Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.subtract Prime
k Gfpx
s Gfpx
t
            s :: Gfpx
s = Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.multiply Prime
k Gfpx
psi_n_2 (Prime -> Gfpx -> Gfpx
Gfpx.square Prime
k Gfpx
psi_n_m1)
            t :: Gfpx
t = Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.multiply Prime
k Gfpx
psi_n_m2 (Prime -> Gfpx -> Gfpx
Gfpx.square Prime
k Gfpx
psi_n_1)

    k :: Prime
k = Curve -> Prime
kCurve Curve
e
    h :: Prime
h = Prime -> Prime -> Prime
Prime.invert Prime
k (Prime -> Prime -> Prime
Prime.fromInteger Prime
k Prime
2)
    f :: Gfpx
f = Prime -> Prime -> Gfpx -> Gfpx
Gfpx.multiplyConstant Prime
k (Prime -> Prime -> Prime
Prime.fromInteger Prime
k Prime
4) (Curve -> Gfpx
rhs Curve
e)

-------------------------------------------------------------------------------
-- Endomorphisms of curve points
--
-- https://math.mit.edu/classes/18.783/2019/LectureNotes9.pdf
-------------------------------------------------------------------------------

data End = End Gfpx Gfpx
  deriving (End -> End -> Bool
(End -> End -> Bool) -> (End -> End -> Bool) -> Eq End
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: End -> End -> Bool
$c/= :: End -> End -> Bool
== :: End -> End -> Bool
$c== :: End -> End -> Bool
Eq,Eq End
Eq End
-> (End -> End -> Ordering)
-> (End -> End -> Bool)
-> (End -> End -> Bool)
-> (End -> End -> Bool)
-> (End -> End -> Bool)
-> (End -> End -> End)
-> (End -> End -> End)
-> Ord End
End -> End -> Bool
End -> End -> Ordering
End -> End -> End
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: End -> End -> End
$cmin :: End -> End -> End
max :: End -> End -> End
$cmax :: End -> End -> End
>= :: End -> End -> Bool
$c>= :: End -> End -> Bool
> :: End -> End -> Bool
$c> :: End -> End -> Bool
<= :: End -> End -> Bool
$c<= :: End -> End -> Bool
< :: End -> End -> Bool
$c< :: End -> End -> Bool
compare :: End -> End -> Ordering
$ccompare :: End -> End -> Ordering
$cp1Ord :: Eq End
Ord)

instance Show End where
  show :: End -> String
show (End Gfpx
x Gfpx
y) = String
"(" String -> ShowS
forall a. [a] -> [a] -> [a]
++ Gfpx -> String
forall a. Show a => a -> String
show Gfpx
x String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
", " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Gfpx -> String
show_y Gfpx
y String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
")"
    where
      show_y :: Gfpx -> String
show_y Gfpx
f | Gfpx -> Bool
Gfpx.isZero Gfpx
f = String
"0"
      show_y Gfpx
f | Gfpx -> Bool
Gfpx.isOne Gfpx
f = String
"y"
      show_y Gfpx
f | Gfpx -> Int
Gfpx.lengthMonomials Gfpx
f Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1 = Gfpx -> String
forall a. Show a => a -> String
show Gfpx
f String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
"y"
      show_y Gfpx
f = String
"(" String -> ShowS
forall a. [a] -> [a] -> [a]
++ Gfpx -> String
forall a. Show a => a -> String
show Gfpx
f String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
")y"

evaluateEnd :: Curve -> End -> Point -> Point
evaluateEnd :: Curve -> End -> Point -> Point
evaluateEnd Curve
_ End
_ Point
Infinity = String -> Point
forall a. HasCallStack => String -> a
error String
"cannot evaluate endomorphism at infinity"
evaluateEnd Curve
e (End Gfpx
f Gfpx
g) (Point Prime
x Prime
y) =
    Prime -> Prime -> Point
Point (Prime -> Gfpx -> Prime -> Prime
Gfpx.evaluate Prime
k Gfpx
f Prime
x) (Prime -> Prime -> Prime -> Prime
Prime.multiply Prime
k (Prime -> Gfpx -> Prime -> Prime
Gfpx.evaluate Prime
k Gfpx
g Prime
x) Prime
y)
  where
    k :: Prime
k = Curve -> Prime
kCurve Curve
e

identityEnd :: Curve -> Gfpx -> End
identityEnd :: Curve -> Gfpx -> End
identityEnd Curve
e Gfpx
h = Gfpx -> Gfpx -> End
End (Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.remainder (Curve -> Prime
kCurve Curve
e) Gfpx
Gfpx.variable Gfpx
h) Gfpx
Gfpx.one

composeEnd :: Curve -> Gfpx -> End -> End -> End
composeEnd :: Curve -> Gfpx -> End -> End -> End
composeEnd Curve
e Gfpx
h (End Gfpx
x1 Gfpx
y1) (End Gfpx
x2 Gfpx
y2) = Gfpx -> Gfpx -> End
End Gfpx
x Gfpx
y
  where
    x :: Gfpx
x = Prime -> Gfpx -> Gfpx -> Gfpx -> Gfpx
Gfpx.composeRemainder Prime
k Gfpx
h Gfpx
x1 Gfpx
x2
    y :: Gfpx
y = Prime -> Gfpx -> Gfpx -> Gfpx -> Gfpx
Gfpx.multiplyRemainder Prime
k Gfpx
h (Prime -> Gfpx -> Gfpx -> Gfpx -> Gfpx
Gfpx.composeRemainder Prime
k Gfpx
h Gfpx
y1 Gfpx
x2) Gfpx
y2
    k :: Prime
k = Curve -> Prime
kCurve Curve
e

negateEnd :: Curve -> End -> End
negateEnd :: Curve -> End -> End
negateEnd Curve
e (End Gfpx
x Gfpx
y) = Gfpx -> Gfpx -> End
End Gfpx
x (Prime -> Gfpx -> Gfpx
Gfpx.negate (Curve -> Prime
kCurve Curve
e) Gfpx
y)

addLambdaEnd :: Curve -> Gfpx -> Gfpx -> Gfpx -> Gfpx -> Gfpx -> Gfpx -> Factor Gfpx End
addLambdaEnd :: Curve
-> Gfpx -> Gfpx -> Gfpx -> Gfpx -> Gfpx -> Gfpx -> Factor Gfpx End
addLambdaEnd Curve
e Gfpx
h Gfpx
n Gfpx
d Gfpx
x1 Gfpx
y1 Gfpx
x2 = do
    Gfpx
l <- Prime -> Gfpx -> Gfpx -> Gfpx -> Factor Gfpx Gfpx
Gfpx.divideRemainderF Prime
k Gfpx
h Gfpx
n Gfpx
d
    let x :: Gfpx
x = Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.subtract Prime
k
              (Prime -> Gfpx -> Gfpx -> Gfpx -> Gfpx
Gfpx.multiplyRemainder Prime
k Gfpx
h (Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.squareRemainder Prime
k Gfpx
h Gfpx
l) Gfpx
f)
              (Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.add Prime
k Gfpx
x1 Gfpx
x2)
    let y :: Gfpx
y = Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.subtract Prime
k
              (Prime -> Gfpx -> Gfpx -> Gfpx -> Gfpx
Gfpx.multiplyRemainder Prime
k Gfpx
h Gfpx
l (Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.subtract Prime
k Gfpx
x1 Gfpx
x)) Gfpx
y1
    End -> Factor Gfpx End
forall (m :: * -> *) a. Monad m => a -> m a
return (End -> Factor Gfpx End) -> End -> Factor Gfpx End
forall a b. (a -> b) -> a -> b
$ Gfpx -> Gfpx -> End
End Gfpx
x Gfpx
y
  where
    f :: Gfpx
f = Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.remainder Prime
k (Curve -> Gfpx
rhs Curve
e) Gfpx
h
    k :: Prime
k = Curve -> Prime
kCurve Curve
e

doubleEnd :: Curve -> Gfpx -> End -> Factor Gfpx End
doubleEnd :: Curve -> Gfpx -> End -> Factor Gfpx End
doubleEnd Curve
e Gfpx
h (End Gfpx
x Gfpx
y) = Curve
-> Gfpx -> Gfpx -> Gfpx -> Gfpx -> Gfpx -> Gfpx -> Factor Gfpx End
addLambdaEnd Curve
e Gfpx
h Gfpx
n Gfpx
d Gfpx
x Gfpx
y Gfpx
x
  where
    n :: Gfpx
n = Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.add Prime
k
          (Prime -> Prime -> Gfpx -> Gfpx
Gfpx.multiplyConstant Prime
k
             (Prime -> Prime -> Prime
Prime.fromInteger Prime
k Prime
3)
             (Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.squareRemainder Prime
k Gfpx
h Gfpx
x))
          (Prime -> Gfpx
Gfpx.constant Prime
a)
    d :: Gfpx
d = Prime -> Prime -> Gfpx -> Gfpx
Gfpx.multiplyConstant Prime
k
          (Prime -> Prime -> Prime
Prime.fromInteger Prime
k Prime
2)
          (Prime -> Gfpx -> Gfpx -> Gfpx -> Gfpx
Gfpx.multiplyRemainder Prime
k Gfpx
h Gfpx
y Gfpx
f)
    f :: Gfpx
f = Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.remainder Prime
k (Curve -> Gfpx
rhs Curve
e) Gfpx
h
    k :: Prime
k = Curve -> Prime
kCurve Curve
e
    a :: Prime
a = Curve -> Prime
aCurve Curve
e

addEnd:: Curve -> Gfpx -> End -> End -> Factor Gfpx End
addEnd :: Curve -> Gfpx -> End -> End -> Factor Gfpx End
addEnd Curve
e Gfpx
h End
p1 End
p2 =
    if Gfpx
x1 Gfpx -> Gfpx -> Bool
forall a. Eq a => a -> a -> Bool
/= Gfpx
x2 then Curve
-> Gfpx -> Gfpx -> Gfpx -> Gfpx -> Gfpx -> Gfpx -> Factor Gfpx End
addLambdaEnd Curve
e Gfpx
h Gfpx
n Gfpx
d Gfpx
x1 Gfpx
y1 Gfpx
x2
    else if Gfpx
y1 Gfpx -> Gfpx -> Bool
forall a. Eq a => a -> a -> Bool
== Gfpx
y2 then Curve -> Gfpx -> End -> Factor Gfpx End
doubleEnd Curve
e Gfpx
h End
p1
    else String -> Factor Gfpx End
forall a. HasCallStack => String -> a
error String
"adding a point and its negation"
  where
    n :: Gfpx
n = Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.subtract Prime
k Gfpx
y2 Gfpx
y1
    d :: Gfpx
d = Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.subtract Prime
k Gfpx
x2 Gfpx
x1
    End Gfpx
x1 Gfpx
y1 = End
p1
    End Gfpx
x2 Gfpx
y2 = End
p2
    k :: Prime
k = Curve -> Prime
kCurve Curve
e

addMultiplyEnd :: Curve -> Gfpx -> End -> End -> Integer -> Factor Gfpx End
addMultiplyEnd :: Curve -> Gfpx -> End -> End -> Prime -> Factor Gfpx End
addMultiplyEnd Curve
_ Gfpx
_ End
z End
_ Prime
0 = End -> Factor Gfpx End
forall a b. b -> Either a b
Right End
z
addMultiplyEnd Curve
e Gfpx
h End
z End
p Prime
n | Prime
n Prime -> Prime -> Bool
forall a. Ord a => a -> a -> Bool
< Prime
0 =
    Curve -> Gfpx -> End -> End -> Prime -> Factor Gfpx End
addMultiplyEnd Curve
e Gfpx
h End
z (Curve -> End -> End
Factor.Ec.negateEnd Curve
e End
p) (-Prime
n)
addMultiplyEnd Curve
e Gfpx
h End
z End
p Prime
n = do
    End
z' <- if Prime -> Bool
forall a. Integral a => a -> Bool
even Prime
n then End -> Factor Gfpx End
forall (m :: * -> *) a. Monad m => a -> m a
return End
z else Curve -> Gfpx -> End -> End -> Factor Gfpx End
addEnd Curve
e Gfpx
h End
z End
p
    End
p' <- Curve -> Gfpx -> End -> Factor Gfpx End
doubleEnd Curve
e Gfpx
h End
p
    Curve -> Gfpx -> End -> End -> Prime -> Factor Gfpx End
addMultiplyEnd Curve
e Gfpx
h End
z' End
p' Prime
n'
  where
    n' :: Prime
n' = Prime
n Prime -> Prime -> Prime
forall a. Integral a => a -> a -> a
`div` Prime
2

multiplyEnd :: Curve -> Gfpx -> End -> Integer -> Factor Gfpx End
multiplyEnd :: Curve -> Gfpx -> End -> Prime -> Factor Gfpx End
multiplyEnd Curve
_ Gfpx
_ End
_ Prime
0 = String -> Factor Gfpx End
forall a. HasCallStack => String -> a
error String
"scalar multiply by zero"
multiplyEnd Curve
e Gfpx
h End
p Prime
n = Curve -> Gfpx -> End -> End -> Prime -> Factor Gfpx End
addMultiplyEnd Curve
e Gfpx
h End
p End
p (Prime
n Prime -> Prime -> Prime
forall a. Num a => a -> a -> a
- Prime
1)

frobeniusEnd :: Curve -> Gfpx -> End
frobeniusEnd :: Curve -> Gfpx -> End
frobeniusEnd Curve
e Gfpx
h = Gfpx -> Gfpx -> End
End Gfpx
x Gfpx
y
  where
    x :: Gfpx
x = Prime -> Gfpx -> Gfpx -> Prime -> Gfpx
Gfpx.expRemainder Prime
k Gfpx
h (Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.remainder Prime
k Gfpx
Gfpx.variable Gfpx
h) Prime
k
    y :: Gfpx
y = Prime -> Gfpx -> Gfpx -> Prime -> Gfpx
Gfpx.expRemainder Prime
k Gfpx
h Gfpx
f ((Prime
k Prime -> Prime -> Prime
forall a. Num a => a -> a -> a
- Prime
1) Prime -> Prime -> Prime
forall a. Integral a => a -> a -> a
`div` Prime
2)
    f :: Gfpx
f = Prime -> Gfpx -> Gfpx -> Gfpx
Gfpx.remainder Prime
k (Curve -> Gfpx
rhs Curve
e) Gfpx
h
    k :: Prime
k = Curve -> Prime
kCurve Curve
e

-------------------------------------------------------------------------------
-- Schoof's algorithm for counting points on the curve
--
-- https://en.wikipedia.org/wiki/Schoof%27s_algorithm
-- https://math.mit.edu/classes/18.783/2019/LectureNotes9.pdf
-------------------------------------------------------------------------------

traceOfFrobeniusMod2 :: Curve -> Integer
traceOfFrobeniusMod2 :: Curve -> Prime
traceOfFrobeniusMod2 Curve
e = if Int -> Bool
forall a. Integral a => a -> Bool
even ([Prime] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length (Prime -> Gfpx -> [Prime]
Gfpx.roots Prime
k Gfpx
f)) then Prime
1 else Prime
0
  where
    f :: Gfpx
f = Curve -> Gfpx
rhs Curve
e
    k :: Prime
k = Curve -> Prime
kCurve Curve
e

traceOfFrobeniusModOddPrime :: Curve -> Prime -> Gfpx -> Integer
traceOfFrobeniusModOddPrime :: Curve -> Prime -> Gfpx -> Prime
traceOfFrobeniusModOddPrime Curve
e Prime
l = Gfpx -> Prime
go
  where
    go :: Gfpx -> Prime
go Gfpx
h = case Gfpx -> Either Gfpx Prime
tr Gfpx
h of
             Left Gfpx
g -> if Gfpx -> Int
Gfpx.degree Gfpx
g Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Gfpx -> Int
Gfpx.degree Gfpx
h then Gfpx -> Prime
go Gfpx
g
                       else String -> Prime
forall a. HasCallStack => String -> a
error String
"not a proper factor"
             Right Prime
n -> Prime
n

    tr :: Gfpx -> Either Gfpx Prime
tr Gfpx
h = do
        End
kl <- Curve -> Gfpx -> End -> Prime -> Factor Gfpx End
multiplyEnd Curve
e Gfpx
h (Curve -> Gfpx -> End
identityEnd Curve
e Gfpx
h) (Prime
k Prime -> Prime -> Prime
forall a. Integral a => a -> a -> a
`mod` Prime
l)
        if End
kl End -> End -> Bool
forall a. Eq a => a -> a -> Bool
== Curve -> End -> End
negateEnd Curve
e End
pil2 then Prime -> Either Gfpx Prime
forall (m :: * -> *) a. Monad m => a -> m a
return Prime
0 else do
          End
pil2_kl <- Curve -> Gfpx -> End -> End -> Factor Gfpx End
addEnd Curve
e Gfpx
h End
pil2 End
kl
          let inc :: Prime -> End -> Either Gfpx Prime
inc Prime
c End
_ | Prime
c Prime -> Prime -> Bool
forall a. Eq a => a -> a -> Bool
== Prime
l = String -> Either Gfpx Prime
forall a. HasCallStack => String -> a
error (String -> Either Gfpx Prime) -> String -> Either Gfpx Prime
forall a b. (a -> b) -> a -> b
$ String
"couldn't find trace mod " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Prime -> String
forall a. Show a => a -> String
show Prime
l
              inc Prime
c End
cpil | End
cpil End -> End -> Bool
forall a. Eq a => a -> a -> Bool
== End
pil2_kl = Prime -> Either Gfpx Prime
forall (m :: * -> *) a. Monad m => a -> m a
return Prime
c
              inc Prime
c End
cpil = Curve -> Gfpx -> End -> End -> Factor Gfpx End
addEnd Curve
e Gfpx
h End
pil End
cpil Factor Gfpx End -> (End -> Either Gfpx Prime) -> Either Gfpx Prime
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= Prime -> End -> Either Gfpx Prime
inc (Prime
c Prime -> Prime -> Prime
forall a. Num a => a -> a -> a
+ Prime
1)
          Prime -> End -> Either Gfpx Prime
inc Prime
1 End
pil
      where
        pil2 :: End
pil2 = Curve -> Gfpx -> End -> End -> End
composeEnd Curve
e Gfpx
h End
pil End
pil
        pil :: End
pil = Curve -> Gfpx -> End
frobeniusEnd Curve
e Gfpx
h

    k :: Prime
k = Curve -> Prime
kCurve Curve
e

traceOfFrobenius :: Curve -> Integer
traceOfFrobenius :: Curve -> Prime
traceOfFrobenius Curve
e = (Prime, Prime) -> [Prime] -> Prime
go (Curve -> Prime
traceOfFrobeniusMod2 Curve
e, Prime
2) ([Prime] -> [Prime]
forall a. [a] -> [a]
tail [Prime]
Prime.primes)
  where
    go :: (Prime, Prime) -> [Prime] -> Prime
go (Prime
t,Prime
m) [Prime]
_ | Prime
b Prime -> Prime -> Bool
forall a. Ord a => a -> a -> Bool
<= Prime
m = Prime -> Prime -> Prime
Prime.toSmallestInteger Prime
m Prime
t
    go (Prime, Prime)
_ [] = String -> Prime
forall a. HasCallStack => String -> a
error String
"ran out of primes"
    go (Prime, Prime)
tm (Prime
l : [Prime]
ls) | Prime
l Prime -> Prime -> Bool
forall a. Eq a => a -> a -> Bool
== Prime
k = (Prime, Prime) -> [Prime] -> Prime
go (Prime, Prime)
tm [Prime]
ls
    go (Prime
t,Prime
m) (Prime
l : [Prime]
ls) = (Prime, Prime) -> [Prime] -> Prime
go (Prime
t',Prime
m') [Prime]
ls
      where
        tl :: Prime
tl = Curve -> Prime -> Gfpx -> Prime
traceOfFrobeniusModOddPrime Curve
e Prime
l ([Gfpx]
psi [Gfpx] -> Int -> Gfpx
forall a. [a] -> Int -> a
!! Prime -> Int
forall a. Num a => Prime -> a
fromInteger Prime
l)
        t' :: Prime
t' = Prime -> Prime -> Prime -> Prime -> Prime
chineseRemainder Prime
l Prime
m Prime
tl Prime
t
        m' :: Prime
m' = Prime
l Prime -> Prime -> Prime
forall a. Num a => a -> a -> a
* Prime
m

    psi :: [Gfpx]
psi = Curve -> [Gfpx]
psiDivisionPolynomials Curve
e
    b :: Prime
b = Prime
2 Prime -> Prime -> Prime
forall a. Num a => a -> a -> a
* Prime -> Prime -> Prime
nthRoot Prime
2 (Prime
4 Prime -> Prime -> Prime
forall a. Num a => a -> a -> a
* Prime
k) Prime -> Prime -> Prime
forall a. Num a => a -> a -> a
+ Prime
1  -- Number of possible values of trace
    k :: Prime
k = Curve -> Prime
kCurve Curve
e

supersingular :: Curve -> Bool
supersingular :: Curve -> Bool
supersingular = Prime -> Prime -> Bool
forall a. Eq a => a -> a -> Bool
(==) Prime
0 (Prime -> Bool) -> (Curve -> Prime) -> Curve -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Curve -> Prime
traceOfFrobenius

order :: Curve -> Integer
order :: Curve -> Prime
order Curve
e = Curve -> Prime
kCurve Curve
e Prime -> Prime -> Prime
forall a. Num a => a -> a -> a
+ Prime
1 Prime -> Prime -> Prime
forall a. Num a => a -> a -> a
- Curve -> Prime
traceOfFrobenius Curve
e

{-
ghci Factor/Ec.hs

let e = Curve 5 3 4
let p1 = Point 3 0
let p2 = Point 3 0
let p3 = Point 0 2
add e (add e p1 p2) p3 == add e p1 (add e p2 p3)
points e

let cfg = defaultConfig
let n = 3119 * 4261
let n = 3119 * 3119
let n = 48029 * 57641
let n = 3119 * 48029 * 57641
let n = 10712543 * 13777067
let n = 2616707501 * 3620408573
let n = 2616707501 ^ 2
let r0 = Random.mkStdGen 90
evalCurvesConfig (curvesConfig cfg) n
factor cfg n r0

let e = Curve 17 13 14
let e = Curve 5 3 4
let e = Curve 7 5 5
let l = (3 :: Integer)
let k = kCurve e
let (_,h) = Gfpx.constMonic k (psiDivisionPolynomials e !! fromInteger l)
traceOfFrobeniusModOddPrime e l h
let pil = frobeniusEnd e h
let pil2 = composeEnd e h pil pil
let Right kl = multiplyEnd e h (identityEnd e h) (k `mod` l)
kl == negateEnd e pil2
addEnd e h pil2 kl
let Right pil2_kl = it
let Left h = it
traceOfFrobenius e
order e

let k = 2616707501
let k = 48029
let r0 = Random.mkStdGen 35
let ((e,p),r1) = uniformCurve k r0
let psi = psiDivisionPolynomials e
let psi_l l = snd (Gfpx.constMonic k (psi !! fromInteger l))
mapM_ (putStrLn . show . (\l -> let h = psi_l l in (traceOfFrobeniusModOddPrime e l h, l, Gfpx.degree h))) (tail Prime.list)
mapM_ (putStrLn . show . (\l -> let h = psi_l l in (l, Gfpx.degree h, head (fst (Gfpx.factorMonic k h r1))))) (tail Prime.list)
-}