Safe Haskell	None
Language	GHC2021

Math.NTT

Synopsis

ntt :: forall (p :: Nat). KnownNat p => Vector (GF p) -> Vector (GF p)
intt :: forall (p :: Nat). KnownNat p => Vector (GF p) -> Vector (GF p)
convolute :: forall (p :: Nat). KnownNat p => Vector (GF p) -> Vector (GF p) -> Vector (GF p)
data NTTRunner (p :: Nat) = NTTRunner {
- sesNR :: !(Vector (GF p))
- siesNR :: !(Vector (GF p))
}
nttRunner :: forall (p :: Nat). KnownNat p => NTTRunner p
butterfly :: forall (p :: Nat) m. (KnownNat p, PrimMonad m) => MVector (PrimState m) (GF p) -> m ()
invButterfly :: forall (p :: Nat) m. (KnownNat p, PrimMonad m) => MVector (PrimState m) (GF p) -> m ()
growToPowerOfTwo :: (Num a, Unbox a) => Vector a -> Vector a
primitiveRoot :: Int -> Int

Documentation

ntt :: forall (p :: Nat). KnownNat p => Vector (GF p) -> Vector (GF p) Source #

Number Theoretic Transform p: prime (c * 2 ^ k + 1)

n = 2 ^ i, n < 2 ^ k

O(n log n)

>>> ntt @998244353 [1,1,1,1]
[4,0,0,0]
>>> ntt @469762049 [123,0,0,0]
[123,123,123,123]

intt :: forall (p :: Nat). KnownNat p => Vector (GF p) -> Vector (GF p) Source #

convolute :: forall (p :: Nat). KnownNat p => Vector (GF p) -> Vector (GF p) -> Vector (GF p) Source #

>>> convolute @998244353 [1,1,1,0] [1,1,1,0]
[1,2,3,2,1,0,0]
>>> convolute @998244353 [1,1,1] [1,1,1,0]
[1,2,3,2,1,0]

Constructors

NTTRunner
Fields sesNR :: !(Vector (GF p)) siesNR :: !(Vector (GF p))

butterfly :: forall (p :: Nat) m. (KnownNat p, PrimMonad m) => MVector (PrimState m) (GF p) -> m () Source #

invButterfly :: forall (p :: Nat) m. (KnownNat p, PrimMonad m) => MVector (PrimState m) (GF p) -> m () Source #

growToPowerOfTwo :: (Num a, Unbox a) => Vector a -> Vector a Source #

>>> growToPowerOfTwo (U.fromListN 3 [1::Int,2,3])
[1,2,3,0]

Arguments

:: Int	prime
-> Int

>>> primitiveRoot 2
1
>>> primitiveRoot 998244353
3