Data.Number.Flint.NMod

Integers mod n (word-size n)

data NMod

Constructors

NMod !(ForeignPtr CNMod)

data CNMod

Constructors

CNMod CMpLimb CMpLimb CFBitCnt

Instances

Storable CNMod

Defined in Data.Number.Flint.NMod.FFI

Methods

sizeOf :: CNMod -> Int

alignment :: CNMod -> Int

peekElemOff :: Ptr CNMod -> Int -> IO CNMod

pokeElemOff :: Ptr CNMod -> Int -> CNMod -> IO ()

peekByteOff :: Ptr b -> Int -> IO CNMod

pokeByteOff :: Ptr b -> Int -> CNMod -> IO ()

peek :: Ptr CNMod -> IO CNMod

poke :: Ptr CNMod -> CNMod -> IO ()

Show CNMod

Defined in Data.Number.Flint.NMod.FFI

Methods

showsPrec :: Int -> CNMod -> ShowS

show :: CNMod -> String

showList :: [CNMod] -> ShowS

Memory management

newNMod :: CMpLimb -> IO NMod

Create a new NMod structure

withNMod :: NMod -> (Ptr CNMod -> IO a) -> IO (NMod, a)

Use NMod structure

withNewNMod :: CMpLimb -> (Ptr CNMod -> IO a) -> IO (NMod, a)

nmod_init :: Ptr CNMod -> CMpLimb -> IO ()

nmod_init mod n

Initialises the given nmod_t structure for reduction modulo \(n\) with a precomputed inverse.

Modular reduction and arithmetic

_nmod_add :: CMpLimb -> CMpLimb -> Ptr CNMod -> IO CMpLimb

_nmod_add a b mod

Returns \(a + b\) modulo mod.n. It is assumed that mod is no more than FLINT_BITS - 1 bits. It is assumed that \(a\) and \(b\) are already reduced modulo mod.n.

nmod_add :: CMpLimb -> CMpLimb -> Ptr CNMod -> IO CMpLimb

nmod_add a b mod

Returns \(a + b\) modulo mod.n. No assumptions are made about mod.n. It is assumed that \(a\) and \(b\) are already reduced modulo mod.n.

_nmod_sub :: CMpLimb -> CMpLimb -> Ptr CNMod -> IO CMpLimb

_nmod_sub a b mod

Returns \(a - b\) modulo mod.n. It is assumed that mod is no more than FLINT_BITS - 1 bits. It is assumed that \(a\) and \(b\) are already reduced modulo mod.n.

nmod_sub :: CMpLimb -> CMpLimb -> Ptr CNMod -> IO CMpLimb

nmod_sub a b mod

Returns \(a - b\) modulo mod.n. No assumptions are made about mod.n. It is assumed that \(a\) and \(b\) are already reduced modulo mod.n.

nmod_neg :: CMpLimb -> Ptr CNMod -> IO CMpLimb

nmod_neg a mod

Returns \(-a\) modulo mod.n. It is assumed that \(a\) is already reduced modulo mod.n, but no assumptions are made about the latter.

nmod_mul :: CMpLimb -> CMpLimb -> Ptr CNMod -> IO CMpLimb

nmod_mul a b mod

Returns \(ab\) modulo mod.n. No assumptions are made about mod.n. It is assumed that \(a\) and \(b\) are already reduced modulo mod.n.

_nmod_mul_fullword :: CMpLimb -> CMpLimb -> Ptr CNMod -> IO CMpLimb

_nmod_mul_fullword a b mod

Returns \(ab\) modulo mod.n. Requires that mod.n is exactly FLINT_BITS large. It is assumed that \(a\) and \(b\) are already reduced modulo mod.n.

nmod_inv :: CMpLimb -> Ptr CNMod -> IO CMpLimb

nmod_inv a mod

Returns \(a^{-1}\) modulo mod.n. The inverse is assumed to exist.

nmod_div :: CMpLimb -> CMpLimb -> Ptr CNMod -> IO CMpLimb

nmod_div a b mod

Returns \(ab^{-1}\) modulo mod.n. The inverse of \(b\) is assumed to exist. It is assumed that \(a\) is already reduced modulo mod.n.

nmod_pow_ui :: CMpLimb -> CULong -> Ptr CNMod -> IO CMpLimb

nmod_pow_ui a e mod

Returns \(a^e\) modulo mod.n. No assumptions are made about mod.n. It is assumed that \(a\) is already reduced modulo mod.n.

Discrete Logarithms via Pohlig-Hellman

data NModDiscreteLogPohligHellman

Constructors

NModDiscreteLogPohligHellman !(ForeignPtr CNModDiscreteLogPohligHellman)

Instances

Storable CNModDiscreteLogPohligHellman

Defined in Data.Number.Flint.NMod.FFI

Methods

sizeOf :: CNModDiscreteLogPohligHellman -> Int

alignment :: CNModDiscreteLogPohligHellman -> Int

peekElemOff :: Ptr CNModDiscreteLogPohligHellman -> Int -> IO CNModDiscreteLogPohligHellman

pokeElemOff :: Ptr CNModDiscreteLogPohligHellman -> Int -> CNModDiscreteLogPohligHellman -> IO ()

peekByteOff :: Ptr b -> Int -> IO CNModDiscreteLogPohligHellman

pokeByteOff :: Ptr b -> Int -> CNModDiscreteLogPohligHellman -> IO ()

peek :: Ptr CNModDiscreteLogPohligHellman -> IO CNModDiscreteLogPohligHellman

poke :: Ptr CNModDiscreteLogPohligHellman -> CNModDiscreteLogPohligHellman -> IO ()

type CNModDiscreteLogPohligHellman = CFlint NModDiscreteLogPohligHellman

nmod_discrete_log_pohlig_hellman_init :: Ptr CNModDiscreteLogPohligHellman -> IO ()

nmod_discrete_log_pohlig_hellman_init L

Initialize L. Upon initialization L is not ready for computation.

nmod_discrete_log_pohlig_hellman_clear :: Ptr CNModDiscreteLogPohligHellman -> IO ()

nmod_discrete_log_pohlig_hellman_clear L

Free any space used by L.

nmod_discrete_log_pohlig_hellman_precompute_prime :: Ptr CNModDiscreteLogPohligHellman -> CMpLimb -> IO CDouble

nmod_discrete_log_pohlig_hellman_precompute_prime L p

Configure L for discrete logarithms modulo p to an internally chosen base. It is assumed that p is prime. The return is an estimate on the number of multiplications needed for one run.

nmod_discrete_log_pohlig_hellman_primitive_root :: Ptr CNModDiscreteLogPohligHellman -> IO CMpLimb

nmod_discrete_log_pohlig_hellman_primitive_root L

Return the internally stored base.

nmod_discrete_log_pohlig_hellman_run :: Ptr CNModDiscreteLogPohligHellman -> CMpLimb -> IO CULong

nmod_discrete_log_pohlig_hellman_run L y

Return the logarithm of y with respect to the internally stored base. y is expected to be reduced modulo the p. The function is undefined if the logarithm does not exist.