Data.Number.Flint.Fmpz.Mod

Arithmetic modulo integers

Context object

data FmpzModCtx

Constructors

FmpzModCtx !(ForeignPtr CFmpzModCtx)

Instances

Storable CFmpzModCtx

Defined in Data.Number.Flint.Fmpz.Mod.FFI

Methods

sizeOf :: CFmpzModCtx -> Int

alignment :: CFmpzModCtx -> Int

peekElemOff :: Ptr CFmpzModCtx -> Int -> IO CFmpzModCtx

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

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

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

peek :: Ptr CFmpzModCtx -> IO CFmpzModCtx

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

type CFmpzModCtx = CFlint FmpzModCtx

newFmpzModCtx :: Fmpz -> IO FmpzModCtx

withFmpzModCtx :: FmpzModCtx -> (Ptr CFmpzModCtx -> IO a) -> IO (FmpzModCtx, a)

withNewFmpzModCtx :: Fmpz -> (Ptr CFmpzModCtx -> IO a) -> IO (FmpzModCtx, a)

fmpz_mod_ctx_init :: Ptr CFmpzModCtx -> Ptr CFmpz -> IO ()

fmpz_mod_ctx_init ctx n

Initialise ctx for arithmetic modulo n, which is expected to be positive.

fmpz_mod_ctx_clear :: Ptr CFmpzModCtx -> IO ()

fmpz_mod_ctx_clear ctx

Free any memory used by ctx.

fmpz_mod_ctx_set_modulus :: Ptr CFmpzModCtx -> Ptr CFmpz -> IO ()

fmpz_mod_ctx_set_modulus ctx n

Reconfigure ctx for arithmetic modulo n.

Conversions

fmpz_mod_set_fmpz :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpzModCtx -> IO ()

fmpz_mod_set_fmpz a b ctx

Set a to b after reduction modulo the modulus.

Arithmetic

fmpz_mod_is_canonical :: Ptr CFmpz -> Ptr CFmpzModCtx -> IO CInt

fmpz_mod_is_canonical a ctx

Return 1 if \(a\) is in the canonical range \([0,n)\) and 0 otherwise.

fmpz_mod_is_one :: Ptr CFmpz -> Ptr CFmpzModCtx -> IO CInt

fmpz_mod_is_one a ctx

Return 1 if \(a\) is \(1\) modulo \(n\) and return 0 otherwise.

fmpz_mod_add :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpzModCtx -> IO ()

fmpz_mod_add a b c ctx

Set \(a\) to \(b+c\) modulo \(n\).

fmpz_mod_add_fmpz :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpzModCtx -> IO ()

fmpz_mod_add_fmpz a b c ctx

Set \(a\) to \(b+c\) modulo \(n\) where only \(b\) is assumed to be canonical.

fmpz_mod_sub :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpzModCtx -> IO ()

fmpz_mod_sub a b c ctx

Set \(a\) to \(b-c\) modulo \(n\).

fmpz_mod_sub_fmpz :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpzModCtx -> IO ()

fmpz_mod_sub_fmpz a b c ctx

Set \(a\) to \(b-c\) modulo \(n\) where only \(b\) is assumed to be canonical.

fmpz_mod_fmpz_sub :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpzModCtx -> IO ()

fmpz_mod_fmpz_sub a b c ctx

Set \(a\) to \(b-c\) modulo \(n\) where only \(c\) is assumed to be canonical.

fmpz_mod_neg :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpzModCtx -> IO ()

fmpz_mod_neg a b ctx

Set \(a\) to \(-b\) modulo \(n\).

fmpz_mod_mul :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpzModCtx -> IO ()

fmpz_mod_mul a b c ctx

Set \(a\) to \(b*c\) modulo \(n\).

fmpz_mod_inv :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpzModCtx -> IO ()

fmpz_mod_inv a b ctx

Set \(a\) to \(b^{-1}\) modulo \(n\). This function expects that \(b\) is invertible modulo \(n\) and throws if this not the case. Invertibility maybe tested with func:fmpz_mod_pow_fmpz or func:fmpz_mod_divides.

fmpz_mod_divides :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpzModCtx -> IO CInt

fmpz_mod_divides a b c ctx

If \(a*c = b \mod n\) has a solution for \(a\) return \(1\) and set \(a\) to such a solution. Otherwise return \(0\) and leave \(a\) undefined.

fmpz_mod_pow_ui :: Ptr CFmpz -> Ptr CFmpz -> CULong -> Ptr CFmpzModCtx -> IO ()

fmpz_mod_pow_ui a b e ctx

Set \(a\) to \(b^e\) modulo \(n\).

fmpz_mod_pow_fmpz :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpzModCtx -> IO CInt

fmpz_mod_pow_fmpz a b e ctx

Try to set \(a\) to \(b^e\) modulo \(n\). If \(e < 0\) and \(b\) is not invertible modulo \(n\), the return is \(0\). Otherwise, the return is \(1\).

Discrete Logarithms via Pohlig-Hellman

fmpz_mod_discrete_log_pohlig_hellman_init :: Ptr CFmpzModDiscreteLogPohligHellmann -> IO ()

fmpz_mod_discrete_log_pohlig_hellman_init L

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

fmpz_mod_discrete_log_pohlig_hellman_clear :: Ptr CFmpzModDiscreteLogPohligHellmann -> IO ()

fmpz_mod_discrete_log_pohlig_hellman_clear L

Free any space used by L.

fmpz_mod_discrete_log_pohlig_hellman_precompute_prime :: Ptr CFmpzModDiscreteLogPohligHellmann -> Ptr CFmpz -> IO CDouble

fmpz_mod_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.

fmpz_mod_discrete_log_pohlig_hellman_primitive_root :: Ptr CFmpzModDiscreteLogPohligHellmann -> IO (Ptr CFmpz)

fmpz_mod_discrete_log_pohlig_hellman_primitive_root L

Return the internally stored base.

fmpz_mod_discrete_log_pohlig_hellman_run :: Ptr CFmpz -> Ptr CFmpzModDiscreteLogPohligHellmann -> Ptr CFmpz -> IO ()

fmpz_mod_discrete_log_pohlig_hellman_run x L y

Set x to 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.

fmpz_next_smooth_prime :: Ptr CFmpz -> Ptr CFmpz -> IO CInt

fmpz_next_smooth_prime a b

Either return \(1\) and set \(a\) to a smooth prime strictly greater than \(b\), or return \(0\) and set \(a\) to \(0\). The smooth primes returned by this function currently have no prime factor of \(a-1\) greater than \(23\), but this should not be relied upon.