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.