Data.Number.Flint.Fmpz

An Fmpz represents an integer. This module implements operations on integers.

Example

Warning: Instances like Show and Num are only avaible for some types without context.

import Data.Number.Flint

main = do 
  let x, y :: Fmpz
      x = 7
      y = 8
      z = x * y
  print z
  print $ factor z

Running main yields:

>>> main
56
[(2,3),(7,1)]

Using the Flint library directly

import Data.Number.Flint

main = do 
  x <- newFmpz
  y <- newFmpz
  z <- newFmpz
  withFmpz x $ \x -> do
    withFmpz y $ \y -> do
      withFmpz z $ \z -> do
        fmpz_set_ui x 7
        fmpz_set_ui y 8
        fmpz_mul z x y
        fmpz_print z
        fac <- newFmpzFactor
        putStr "\n"
        withFmpzFactor fac $ \fac -> do
           fmpz_factor fac z
           fmpz_factor_print fac
           putStr "\n"

Running main yields:

>>> main
56
2^3 * 7

Integers Fmpz

data Fmpz

Integer (opaque pointer)

Instances

FlintExpression Fmpz

Defined in Data.Number.Flint.Calcium.Fexpr.Instances

Methods

toFexpr :: Fmpz -> IO Fexpr

UFD Fmpz

Defined in Data.Number.Flint.Fmpz.Instances

Methods

factor :: Fmpz -> [(Fmpz, Int)]

unfactor :: [(Fmpz, Int)] -> Fmpz

Arbitrary Fmpz

Defined in Data.Number.Flint.Fmpz.Instances

Methods

arbitrary :: Gen Fmpz

shrink :: Fmpz -> [Fmpz]

Storable CFmpz

Defined in Data.Number.Flint.Fmpz.FFI

Methods

sizeOf :: CFmpz -> Int

alignment :: CFmpz -> Int

peekElemOff :: Ptr CFmpz -> Int -> IO CFmpz

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

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

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

peek :: Ptr CFmpz -> IO CFmpz

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

Enum Fmpz

Defined in Data.Number.Flint.Fmpz.Instances

Methods

succ :: Fmpz -> Fmpz

pred :: Fmpz -> Fmpz

toEnum :: Int -> Fmpz

fromEnum :: Fmpz -> Int

enumFrom :: Fmpz -> [Fmpz]

enumFromThen :: Fmpz -> Fmpz -> [Fmpz]

enumFromTo :: Fmpz -> Fmpz -> [Fmpz]

enumFromThenTo :: Fmpz -> Fmpz -> Fmpz -> [Fmpz]

Num Fmpz

Defined in Data.Number.Flint.Fmpz.Instances

Methods

(+) :: Fmpz -> Fmpz -> Fmpz

(-) :: Fmpz -> Fmpz -> Fmpz

(*) :: Fmpz -> Fmpz -> Fmpz

negate :: Fmpz -> Fmpz

abs :: Fmpz -> Fmpz

signum :: Fmpz -> Fmpz

fromInteger :: Integer -> Fmpz

Read Fmpz

Defined in Data.Number.Flint.Fmpz.Instances

Methods

readsPrec :: Int -> ReadS Fmpz

readList :: ReadS [Fmpz]

readPrec :: ReadPrec Fmpz

readListPrec :: ReadPrec [Fmpz]

Integral Fmpz

Defined in Data.Number.Flint.Fmpz.Instances

Methods

quot :: Fmpz -> Fmpz -> Fmpz

rem :: Fmpz -> Fmpz -> Fmpz

div :: Fmpz -> Fmpz -> Fmpz

mod :: Fmpz -> Fmpz -> Fmpz

quotRem :: Fmpz -> Fmpz -> (Fmpz, Fmpz)

divMod :: Fmpz -> Fmpz -> (Fmpz, Fmpz)

toInteger :: Fmpz -> Integer

Real Fmpz

Defined in Data.Number.Flint.Fmpz.Instances

Methods

toRational :: Fmpz -> Rational

Show Fmpz

Defined in Data.Number.Flint.Fmpz.Instances

Methods

showsPrec :: Int -> Fmpz -> ShowS

show :: Fmpz -> String

showList :: [Fmpz] -> ShowS

Eq Fmpz

Defined in Data.Number.Flint.Fmpz.Instances

Methods

(==) :: Fmpz -> Fmpz -> Bool

(/=) :: Fmpz -> Fmpz -> Bool

Ord Fmpz

Defined in Data.Number.Flint.Fmpz.Instances

Methods

compare :: Fmpz -> Fmpz -> Ordering

(<) :: Fmpz -> Fmpz -> Bool

(<=) :: Fmpz -> Fmpz -> Bool

(>) :: Fmpz -> Fmpz -> Bool

(>=) :: Fmpz -> Fmpz -> Bool

max :: Fmpz -> Fmpz -> Fmpz

min :: Fmpz -> Fmpz -> Fmpz

Quotient Fmpq Fmpz

Defined in Data.Number.Flint.Fmpq.FFI

Methods

(//) :: Fmpz -> Fmpz -> Fmpq

numerator :: Fmpq -> Fmpz

denominator :: Fmpq -> Fmpz

type CFmpz = CFlint Fmpz

Constructors

newFmpz :: IO Fmpz

newFmpz

Create a new Fmpz.

withFmpz :: Fmpz -> (Ptr CFmpz -> IO a) -> IO (Fmpz, a)

withFmpz x f

Apply f to x.

withNewFmpz :: (Ptr CFmpz -> IO a) -> IO (Fmpz, a)

withNewFmpz f

Apply f to a new Fmpz.

Precomputed inverse

data FmpzPreInvN

Data structure containing the CFmpz pointer

Constructors

FmpzPreInvN !(ForeignPtr CFmpzPreInvN)

type CFmpzPreInvN = CFlint FmpzPreInvN

Factorization structure FmpzFactor

data FmpzFactor

Data structure containing CFmpzFactor pointer

Constructors

FmpzFactor !(ForeignPtr CFmpzFactor)

data CFmpzFactor

Constructors

CFmpzFactor CInt (Ptr CFmpz) (Ptr CULong) CLong CLong

Instances

Storable CFmpzFactor

Defined in Data.Number.Flint.Fmpz.FFI

Methods

sizeOf :: CFmpzFactor -> Int

alignment :: CFmpzFactor -> Int

peekElemOff :: Ptr CFmpzFactor -> Int -> IO CFmpzFactor

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

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

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

peek :: Ptr CFmpzFactor -> IO CFmpzFactor

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

Memory management mpz

_fmpz_new_mpz :: IO (Ptr CMpz)

_fmpz_new_mpz

initialises a new mpz_t and returns a pointer to it. This is only used internally.

_fmpz_cleanup_mpz_content :: IO ()

_fmpz_cleanup_mpz_content

this function does nothing in the reentrant version of fmpz.

_fmpz_cleanup :: IO ()

_fmpz_cleanup

this function does nothing in the reentrant version of fmpz.

_fmpz_promote :: Ptr CFmpz -> IO (Ptr CMpz)

_fmpz_promote f

if \(f\) doesn't represent an mpz_t, initialise one and associate it to \(f\).

_fmpz_promote_val :: Ptr CFmpz -> IO (Ptr CMpz)

_fmpz_promote_val f

if \(f\) doesn't represent an mpz_t, initialise one and associate it to \(f\), but preserve the value of \(f\).

This function is for internal use. The resulting fmpz will be backed by an mpz_t that can be passed to GMP, but the fmpz will be in an inconsistent state with respect to the other Flint fmpz functions such as fmpz_is_zero, etc.

_fmpz_demote :: Ptr CFmpz -> IO ()

_fmpz_demote f

if \(f\) represents an mpz_t clear it and make \(f\) just represent an slong.

_fmpz_demote_val :: Ptr CFmpz -> IO ()

_fmpz_demote_val f

if \(f\) represents an mpz_t and its value will fit in an slong, preserve the value in \(f\) which we make to represent an slong, and clear the mpz_t.

Memory management

fmpz_init :: Ptr CFmpz -> IO ()

fmpz_init f

A small fmpz_t is initialised, i.e.just a slong. The value is set to zero.

fmpz_init2 :: Ptr CFmpz -> CULong -> IO ()

fmpz_init2 f limbs

Initialises the given fmpz_t to have space for the given number of limbs.

If limbs is zero then a small fmpz_t is allocated, i.e.just a slong. The value is also set to zero. It is not necessary to call this function except to save time. A call to fmpz_init will do just fine.

fmpz_clear :: Ptr CFmpz -> IO ()

fmpz_clear f

Clears the given fmpz_t, releasing any memory associated with it, either back to the stack or the OS, depending on whether the reentrant or non-reentrant version of FLINT is built.

fmpz_init_set :: Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_init_set_ui :: Ptr CFmpz -> CULong -> IO ()

fmpz_init_set_si :: Ptr CFmpz -> CLong -> IO ()

fmpz_init_set_si f g

Initialises \(f\) and sets it to the value of \(g\).

Random generation

fmpz_randbits :: Ptr CFmpz -> Ptr CFRandState -> CFBitCnt -> IO ()

fmpz_randbits f state bits

Generates a random signed integer whose absolute value has precisely the given number of bits.

fmpz_randtest :: Ptr CFmpz -> Ptr CFRandState -> CFBitCnt -> IO ()

fmpz_randtest f state bits

Generates a random signed integer whose absolute value has a number of bits which is random from \(0\) up to bits inclusive.

fmpz_randtest_unsigned :: Ptr CFmpz -> Ptr CFRandState -> CFBitCnt -> IO ()

fmpz_randtest_unsigned f state bits

Generates a random unsigned integer whose value has a number of bits which is random from \(0\) up to bits inclusive.

fmpz_randtest_not_zero :: Ptr CFmpz -> Ptr CFRandState -> CFBitCnt -> IO ()

fmpz_randtest_not_zero f state bits

As per fmpz_randtest, but the result will not be \(0\). If bits is set to \(0\), an exception will result.

fmpz_randm :: Ptr CFmpz -> Ptr CFRandState -> Ptr CFmpz -> IO ()

fmpz_randm f state m

Generates a random integer in the range \(0\) to \(m - 1\) inclusive.

fmpz_randtest_mod :: Ptr CFmpz -> Ptr CFRandState -> Ptr CFmpz -> IO ()

fmpz_randtest_mod f state m

Generates a random integer in the range \(0\) to \(m - 1\) inclusive, with an increased probability of generating values close to the endpoints.

fmpz_randtest_mod_signed :: Ptr CFmpz -> Ptr CFRandState -> Ptr CFmpz -> IO ()

fmpz_randtest_mod_signed f state m

Generates a random integer in the range \((-m/2, m/2]\), with an increased probability of generating values close to the endpoints or close to zero.

fmpz_randprime :: Ptr CFmpz -> Ptr CFRandState -> CFBitCnt -> CInt -> IO ()

fmpz_randprime f state bits proved

Generates a random prime number with the given number of bits.

The generation is performed by choosing a random number and then finding the next largest prime, and therefore does not quite give a uniform distribution over the set of primes with that many bits.

Random number generation is performed using the standard Flint random number generator, which is not suitable for cryptographic use.

If proved is nonzero, then the integer returned is guaranteed to actually be prime.

Conversion

fmpz_get_si :: Ptr CFmpz -> IO CLong

fmpz_get_si f

Returns \(f\) as a slong. The result is undefined if \(f\) does not fit into a slong.

fmpz_get_ui :: Ptr CFmpz -> IO CULong

fmpz_get_ui f

Returns \(f\) as an ulong. The result is undefined if \(f\) does not fit into an ulong or is negative.

fmpz_get_uiui :: Ptr CMpLimb -> Ptr CMpLimb -> Ptr CFmpz -> IO ()

fmpz_get_uiui hi low f

If \(f\) consists of two limbs, then *hi and *low are set to the high and low limbs, otherwise *low is set to the low limb and *hi is set to \(0\).

fmpz_get_nmod :: Ptr CFmpz -> Ptr CNMod -> IO CMpLimb

fmpz_get_nmod f mod

Returns \(f \mod n\).

fmpz_get_d :: Ptr CFmpz -> IO CDouble

fmpz_get_d f

Returns \(f\) as a double, rounding down towards zero if \(f\) cannot be represented exactly. The outcome is undefined if \(f\) is too large to fit in the normal range of a double.

fmpz_set_mpf :: Ptr CFmpz -> Ptr CMpf -> IO ()

fmpz_set_mpf f x

Sets \(f\) to the mpf_t \(x\), rounding down towards zero if the value of \(x\) is fractional.

fmpz_get_mpf :: Ptr CMpf -> Ptr CFmpz -> IO ()

fmpz_get_mpf x f

Sets the value of the mpf_t \(x\) to the value of \(f\).

fmpz_get_mpfr :: Ptr CMpfr -> Ptr CFmpz -> CMpfrRnd -> IO ()

fmpz_get_mpfr x f rnd

Sets the value of \(x\) from \(f\), rounded toward the given direction rnd.

fmpz_get_d_2exp :: Ptr CLong -> Ptr CFmpz -> IO CDouble

fmpz_get_d_2exp exp f

Returns \(f\) as a normalized double along with a \(2\)-exponent exp, i.e.if \(r\) is the return value then \(f = r 2^{exp}\), to within 1 ULP.

fmpz_get_mpz :: Ptr CMpz -> Ptr CFmpz -> IO ()

fmpz_get_mpz x f

Sets the mpz_t \(x\) to the same value as \(f\).

fmpz_get_mpn :: Ptr CMp -> Ptr CFmpz -> IO CInt

fmpz_get_mpn n n_in

Sets the mp_ptr \(n\) to the same value as \(n_{in}\). Returned integer is number of limbs allocated to \(n\), minimum number of limbs required to hold the value stored in \(n_{in}\).

fmpz_get_str :: CString -> CInt -> Ptr CFmpz -> IO CString

fmpz_get_str str b f

Returns the representation of \(f\) in base \(b\), which can vary between \(2\) and \(62\), inclusive.

If str is NULL, the result string is allocated by the function. Otherwise, it is up to the caller to ensure that the allocated block of memory is sufficiently large.

fmpz_set_si :: Ptr CFmpz -> CLong -> IO ()

fmpz_set_si f val

Sets \(f\) to the given slong value.

fmpz_set_ui :: Ptr CFmpz -> CULong -> IO ()

fmpz_set_ui f val

Sets \(f\) to the given ulong value.

fmpz_set_d :: Ptr CFmpz -> CDouble -> IO ()

fmpz_set_d f c

Sets \(f\) to the double \(c\), rounding down towards zero if the value of \(c\) is fractional. The outcome is undefined if \(c\) is infinite, not-a-number, or subnormal.

fmpz_set_d_2exp :: Ptr CFmpz -> CDouble -> CLong -> IO ()

fmpz_set_d_2exp f d exp

Sets \(f\) to the nearest integer to \(d 2^{exp}\).

fmpz_neg_ui :: Ptr CFmpz -> CULong -> IO ()

fmpz_neg_ui f val

Sets \(f\) to the given ulong value, and then negates \(f\).

fmpz_set_uiui :: Ptr CFmpz -> CMpLimb -> CMpLimb -> IO ()

fmpz_set_uiui f hi lo

Sets \(f\) to lo, plus hi shifted to the left by FLINT_BITS.

fmpz_neg_uiui :: Ptr CFmpz -> CMpLimb -> CMpLimb -> IO ()

fmpz_neg_uiui f hi lo

Sets \(f\) to lo, plus hi shifted to the left by FLINT_BITS, and then negates \(f\).

fmpz_set_signed_uiui :: Ptr CFmpz -> CULong -> CULong -> IO ()

fmpz_set_signed_uiui f hi lo

Sets \(f\) to lo, plus hi shifted to the left by FLINT_BITS, interpreted as a signed two's complement integer with 2 * FLINT_BITS bits.

fmpz_set_signed_uiuiui :: Ptr CFmpz -> CULong -> CULong -> CULong -> IO ()

fmpz_set_signed_uiuiui f hi mid lo

Sets \(f\) to lo, plus mid shifted to the left by FLINT_BITS, plus hi shifted to the left by 2*FLINT_BITS bits, interpreted as a signed two's complement integer with 3 * FLINT_BITS bits.

fmpz_set_ui_array :: Ptr CFmpz -> Ptr CULong -> CLong -> IO ()

fmpz_set_ui_array out in n

Sets out to the nonnegative integer in[0] + in[1]*X + ... + in[n - 1]*X^(n - 1) where X = 2^FLINT_BITS. It is assumed that n > 0.

fmpz_set_signed_ui_array :: Ptr CFmpz -> Ptr CULong -> CLong -> IO ()

fmpz_set_signed_ui_array out in n

Sets out to the integer represented in in[0], ..., in[n - 1] as a signed two's complement integer with n * FLINT_BITS bits. It is assumed that n > 0. The function operates as a call to fmpz_set_ui_array followed by a symmetric remainder modulo \(2^(n*FLINT\_BITS)\).

fmpz_get_ui_array :: Ptr CULong -> CLong -> Ptr CFmpz -> IO ()

fmpz_get_ui_array out n in

Assuming that the nonnegative integer in can be represented in the form out[0] + out[1]*X + ... + out[n - 1]*X^(n - 1), where \(X = 2^{FLINT\_BITS}\), sets the corresponding elements of out so that this is true. It is assumed that n > 0.

fmpz_get_signed_ui_array :: Ptr CULong -> CLong -> Ptr CFmpz -> IO ()

fmpz_get_signed_ui_array out n in

Retrieves the value of \(in\) modulo \(2^{n * FLINT\_BITS}\) and puts the \(n\) words of the result in out[0], ..., out[n-1]. This will give a signed two's complement representation of \(in\) (assuming \(in\) doesn't overflow the array).

fmpz_get_signed_uiui :: Ptr CULong -> Ptr CULong -> Ptr CFmpz -> IO ()

fmpz_get_signed_uiui hi lo in

Retrieves the value of \(in\) modulo \(2^{2 * FLINT\_BITS}\) and puts the high and low words into *hi and *lo respectively.

fmpz_set_mpz :: Ptr CFmpz -> Ptr CMpz -> IO ()

fmpz_set_mpz f x

Sets \(f\) to the given mpz_t value.

fmpz_set_str :: Ptr CFmpz -> CString -> CInt -> IO CInt

fmpz_set_str f str b

Sets \(f\) to the value given in the null-terminated string str, in base \(b\). The base \(b\) can vary between \(2\) and \(62\), inclusive. Returns \(0\) if the string contains a valid input and \(-1\) otherwise.

fmpz_set_ui_smod :: Ptr CFmpz -> CMpLimb -> CMpLimb -> IO ()

fmpz_set_ui_smod f x m

Sets \(f\) to the signed remainder \(y \equiv x \bmod m\) satisfying \(-m/2 < y \leq m/2\), given \(x\) which is assumed to satisfy \(0 \leq x < m\).

flint_mpz_init_set_readonly :: Ptr CMpz -> Ptr CFmpz -> IO ()

flint_mpz_init_set_readonly z f

Sets the uninitialised mpz_t \(z\) to the value of the readonly fmpz_t \(f\).

Note that it is assumed that \(f\) does not change during the lifetime of \(z\).

The integer \(z\) has to be cleared by a call to flint_mpz_clear_readonly.

The suggested use of the two functions is as follows:

fmpz_t f;
...
{
    mpz_t z;

    flint_mpz_init_set_readonly(z, f);
    foo(..., z);
    flint_mpz_clear_readonly(z);
}

This provides a convenient function for user code, only requiring to work with the types fmpz_t and mpz_t.

In critical code, the following approach may be favourable:

fmpz_t f;
...
{
    __mpz_struct *z;

    z = _fmpz_promote_val(f);
    foo(..., z);
    _fmpz_demote_val(f);
}

flint_mpz_clear_readonly :: Ptr CMpz -> IO ()

flint_mpz_clear_readonly z

Clears the readonly mpz_t \(z\).

fmpz_init_set_readonly :: Ptr CFmpz -> Ptr CMpz -> IO ()

fmpz_init_set_readonly f z

Sets the uninitialised fmpz_t \(f\) to a readonly version of the integer \(z\).

Note that the value of \(z\) is assumed to remain constant throughout the lifetime of \(f\).

The fmpz_t \(f\) has to be cleared by calling the function fmpz_clear_readonly.

The suggested use of the two functions is as follows:

mpz_t z;
...
{
    fmpz_t f;

    fmpz_init_set_readonly(f, z);
    foo(..., f);
    fmpz_clear_readonly(f);
}

fmpz_clear_readonly :: Ptr CFmpz -> IO ()

fmpz_clear_readonly f

Clears the readonly fmpz_t \(f\).

Input and output

fmpz_read :: Ptr CFmpz -> IO CInt

fmpz_read f

Reads a multiprecision integer from stdin. The format is an optional minus sign, followed by one or more digits. The first digit should be non-zero unless it is the only digit.

In case of success, returns a positive number. In case of failure, returns a non-positive number.

This convention is adopted in light of the return values of scanf from the standard library and mpz_inp_str from MPIR.

fmpz_fread :: Ptr CFile -> Ptr CFmpz -> IO CInt

fmpz_fread file f

Reads a multiprecision integer from the stream file. The format is an optional minus sign, followed by one or more digits. The first digit should be non-zero unless it is the only digit.

In case of success, returns a positive number. In case of failure, returns a non-positive number.

This convention is adopted in light of the return values of scanf from the standard library and mpz_inp_str from MPIR.

fmpz_inp_raw :: Ptr CFmpz -> Ptr CFile -> IO (Ptr CSize)

fmpz_inp_raw x fin

Reads a multiprecision integer from the stream file. The format is raw binary format write by fmpz_out_raw.

In case of success, return a positive number, indicating number of bytes read. In case of failure 0.

This function calls the mpz_inp_raw function in library gmp. So that it can read the raw data written by mpz_inp_raw directly.

fmpz_print :: Ptr CFmpz -> IO CInt

fmpz_print x

Prints the value \(x\) to stdout, without a carriage return(CR). The value is printed as either \(0\), the decimal digits of a positive integer, or a minus sign followed by the digits of a negative integer.

In case of success, returns a positive number. In case of failure, returns a non-positive number.

This convention is adopted in light of the return values of flint_printf from the standard library and mpz_out_str from MPIR.

fmpz_fprint :: Ptr CFile -> Ptr CFmpz -> IO CInt

fmpz_fprint file x

Prints the value \(x\) to file, without a carriage return(CR). The value is printed as either \(0\), the decimal digits of a positive integer, or a minus sign followed by the digits of a negative integer.

In case of success, returns a positive number. In case of failure, returns a non-positive number.

This convention is adopted in light of the return values of flint_printf from the standard library and mpz_out_str from MPIR.

fmpz_out_raw :: Ptr CFile -> Ptr CFmpz -> IO (Ptr CSize)

fmpz_out_raw fout x

Writes the value \(x\) to file. The value is written in raw binary format. The integer is written in portable format, with 4 bytes of size information, and that many bytes of limbs. Both the size and the limbs are written in decreasing significance order (i.e., in big-endian).

The output can be read with fmpz_inp_raw.

In case of success, return a positive number, indicating number of bytes written. In case of failure, return 0.

The output of this can also be read by mpz_inp_raw from GMP >= 2, Since this function calls the mpz_inp_raw function in library gmp.

Basic properties and manipulation

fmpz_sizeinbase :: Ptr CFmpz -> CInt -> IO (Ptr CSize)

fmpz_sizeinbase f b

Returns the size of the absolute value of \(f\) in base \(b\), measured in numbers of digits. The base \(b\) can be between \(2\) and \(62\), inclusive.

fmpz_bits :: Ptr CFmpz -> IO CFBitCnt

fmpz_bits f

Returns the number of bits required to store the absolute value of \(f\). If \(f\) is \(0\) then \(0\) is returned.

fmpz_size :: Ptr CFmpz -> IO CMpSize

fmpz_size f

Returns the number of limbs required to store the absolute value of \(f\). If \(f\) is zero then \(0\) is returned.

fmpz_sgn :: Ptr CFmpz -> IO CInt

fmpz_sgn f

Returns \(-1\) if the sign of \(f\) is negative, \(+1\) if it is positive, otherwise returns \(0\).

fmpz_val2 :: Ptr CFmpz -> IO CFBitCnt

fmpz_val2 f

Returns the exponent of the largest power of two dividing \(f\), or equivalently the number of trailing zeros in the binary expansion of \(f\). If \(f\) is zero then \(0\) is returned.

fmpz_swap :: Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_swap f g

Efficiently swaps \(f\) and \(g\). No data is copied.

fmpz_set :: Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_set f g

Sets \(f\) to the same value as \(g\).

fmpz_zero :: Ptr CFmpz -> IO ()

fmpz_zero f

Sets \(f\) to zero.

fmpz_one :: Ptr CFmpz -> IO ()

fmpz_one f

Sets \(f\) to one.

fmpz_abs_fits_ui :: Ptr CFmpz -> IO CInt

fmpz_abs_fits_ui f

Returns whether the absolute value of \(f\) fits into an ulong.

fmpz_fits_si :: Ptr CFmpz -> IO CInt

fmpz_fits_si f

Returns whether the value of \(f\) fits into a slong.

fmpz_setbit :: Ptr CFmpz -> CULong -> IO ()

fmpz_setbit f i

Sets bit index \(i\) of \(f\).

fmpz_tstbit :: Ptr CFmpz -> CULong -> IO CInt

fmpz_tstbit f i

Test bit index \(i\) of \(f\) and return \(0\) or \(1\), accordingly.

fmpz_abs_lbound_ui_2exp :: Ptr CLong -> Ptr CFmpz -> CInt -> IO CMpLimb

fmpz_abs_lbound_ui_2exp exp x bits

For nonzero \(x\), returns a mantissa \(m\) with exactly bits bits and sets exp to an exponent \(e\), such that \(|x| \ge m 2^e\). The number of bits must be between 1 and FLINT_BITS inclusive. The mantissa is guaranteed to be correctly rounded.

fmpz_abs_ubound_ui_2exp :: Ptr CLong -> Ptr CFmpz -> CInt -> IO CMpLimb

fmpz_abs_ubound_ui_2exp exp x bits

For nonzero \(x\), returns a mantissa \(m\) with exactly bits bits and sets exp to an exponent \(e\), such that \(|x| \le m 2^e\). The number of bits must be between 1 and FLINT_BITS inclusive. The mantissa is either correctly rounded or one unit too large (possibly meaning that the exponent is one too large, if the mantissa is a power of two).

Comparison

fmpz_cmp :: Ptr CFmpz -> Ptr CFmpz -> IO CInt

fmpz_cmp_ui :: Ptr CFmpz -> CULong -> IO CInt

fmpz_cmp_si :: Ptr CFmpz -> CLong -> IO CInt

fmpz_cmp_si f g

Returns a negative value if \(f < g\), positive value if \(g < f\), otherwise returns \(0\).

fmpz_cmpabs :: Ptr CFmpz -> Ptr CFmpz -> IO CInt

fmpz_cmpabs f g

Returns a negative value if \(\lvert f\rvert < \lvert g\rvert\), positive value if \(\lvert g\rvert < \lvert f \rvert\), otherwise returns \(0\).

fmpz_cmp2abs :: Ptr CFmpz -> Ptr CFmpz -> IO CInt

fmpz_cmp2abs f g

Returns a negative value if \(\lvert f\rvert < \lvert 2g\rvert\), positive value if \(\lvert 2g\rvert < \lvert f \rvert\), otherwise returns \(0\).

fmpz_equal :: Ptr CFmpz -> Ptr CFmpz -> IO CInt

fmpz_equal_ui :: Ptr CFmpz -> CULong -> IO CInt

fmpz_equal_si :: Ptr CFmpz -> CLong -> IO CInt

fmpz_equal_si f g

Returns \(1\) if \(f\) is equal to \(g\), otherwise returns \(0\).

fmpz_is_zero :: Ptr CFmpz -> IO CInt

fmpz_is_zero f

Returns \(1\) if \(f\) is \(0\), otherwise returns \(0\).

fmpz_is_one :: Ptr CFmpz -> IO CInt

fmpz_is_one f

Returns \(1\) if \(f\) is equal to one, otherwise returns \(0\).

fmpz_is_pm1 :: Ptr CFmpz -> IO CInt

fmpz_is_pm1 f

Returns \(1\) if \(f\) is equal to one or minus one, otherwise returns \(0\).

fmpz_is_even :: Ptr CFmpz -> IO CInt

fmpz_is_even f

Returns whether the integer \(f\) is even.

fmpz_is_odd :: Ptr CFmpz -> IO CInt

fmpz_is_odd f

Returns whether the integer \(f\) is odd.

Basic arithmetic

fmpz_neg :: Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_neg f1 f2

Sets \(f_1\) to \(-f_2\).

fmpz_abs :: Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_abs f1 f2

Sets \(f_1\) to the absolute value of \(f_2\).

fmpz_add :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_add f g h

Sets \(f\) to \(g + h\).

fmpz_add_ui :: Ptr CFmpz -> Ptr CFmpz -> CULong -> IO ()

fmpz_add_si :: Ptr CFmpz -> Ptr CFmpz -> CLong -> IO ()

fmpz_sub :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_sub f g h

Sets \(f\) to \(g - h\).

fmpz_sub_ui :: Ptr CFmpz -> Ptr CFmpz -> CULong -> IO ()

fmpz_sub_si :: Ptr CFmpz -> Ptr CFmpz -> CLong -> IO ()

fmpz_mul :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_mul f g h

Sets \(f\) to \(g \times h\).

fmpz_mul_ui :: Ptr CFmpz -> Ptr CFmpz -> CULong -> IO ()

fmpz_mul_si :: Ptr CFmpz -> Ptr CFmpz -> CLong -> IO ()

fmpz_mul2_uiui :: Ptr CFmpz -> Ptr CFmpz -> CULong -> CULong -> IO ()

fmpz_mul2_uiui f g x y

Sets \(f\) to \(g \times x \times y\) where \(x\) and \(y\) are of type ulong.

fmpz_mul_2exp :: Ptr CFmpz -> Ptr CFmpz -> CULong -> IO ()

fmpz_mul_2exp f g e

Sets \(f\) to \(g \times 2^e\).

Note: Assumes that e + FLINT_BITS does not overflow.

fmpz_one_2exp :: Ptr CFmpz -> CULong -> IO ()

fmpz_one_2exp f e

Sets \(f\) to \(2^e\).

fmpz_addmul :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_addmul f g h

Sets \(f\) to \(f + g \times h\).

fmpz_addmul_ui :: Ptr CFmpz -> Ptr CFmpz -> CULong -> IO ()

fmpz_addmul_si :: Ptr CFmpz -> Ptr CFmpz -> CLong -> IO ()

fmpz_submul :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_submul f g h

Sets \(f\) to \(f - g \times h\).

fmpz_submul_ui :: Ptr CFmpz -> Ptr CFmpz -> CULong -> IO ()

fmpz_submul_si :: Ptr CFmpz -> Ptr CFmpz -> CLong -> IO ()

fmpz_fmma :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_fmma f a b c d

Sets \(f\) to \(a \times b + c \times d\).

fmpz_fmms :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_fmms f a b c d

Sets \(f\) to \(a \times b - c \times d\).

fmpz_cdiv_qr :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_fdiv_qr :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_tdiv_qr :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_ndiv_qr :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_cdiv_q :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_fdiv_q :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_tdiv_q :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_cdiv_q_si :: Ptr CFmpz -> Ptr CFmpz -> CLong -> IO ()

fmpz_fdiv_q_si :: Ptr CFmpz -> Ptr CFmpz -> CLong -> IO ()

fmpz_tdiv_q_si :: Ptr CFmpz -> Ptr CFmpz -> CLong -> IO ()

fmpz_cdiv_q_ui :: Ptr CFmpz -> Ptr CFmpz -> CULong -> IO ()

fmpz_fdiv_q_ui :: Ptr CFmpz -> Ptr CFmpz -> CULong -> IO ()

fmpz_tdiv_q_ui :: Ptr CFmpz -> Ptr CFmpz -> CULong -> IO ()

fmpz_cdiv_q_2exp :: Ptr CFmpz -> Ptr CFmpz -> CULong -> IO ()

fmpz_fdiv_q_2exp :: Ptr CFmpz -> Ptr CFmpz -> CULong -> IO ()

fmpz_tdiv_q_2exp :: Ptr CFmpz -> Ptr CFmpz -> CULong -> IO ()

fmpz_fdiv_r :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_cdiv_r_2exp :: Ptr CFmpz -> Ptr CFmpz -> CULong -> IO ()

fmpz_fdiv_r_2exp :: Ptr CFmpz -> Ptr CFmpz -> CULong -> IO ()

fmpz_tdiv_r_2exp :: Ptr CFmpz -> Ptr CFmpz -> CULong -> IO ()

fmpz_tdiv_r_2exp s g exp

Sets \(f\) to the quotient of \(g\) by \(h\) and/or \(s\) to the remainder. For the 2exp functions, g = 2^exp. \(If :math:`h\) is \(0\) an exception is raised.

Rounding is made in the following way:

• fdiv rounds the quotient via floor rounding.
• cdiv rounds the quotient via ceil rounding.
• tdiv rounds the quotient via truncation, i.e. rounding towards zero.
• ndiv rounds the quotient such that the remainder has the smallest absolute value. In case of ties, it rounds the quotient towards zero.

fmpz_cdiv_ui :: Ptr CFmpz -> CULong -> IO CULong

fmpz_fdiv_ui :: Ptr CFmpz -> CULong -> IO CULong

fmpz_tdiv_ui :: Ptr CFmpz -> CULong -> IO CULong

fmpz_tdiv_ui g h

Returns the absolute value remainder of \(g\) divided by \(h\), following the convention of rounding as seen above. If \(h\) is zero an exception is raised.

fmpz_divexact :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_divexact_si :: Ptr CFmpz -> Ptr CFmpz -> CLong -> IO ()

fmpz_divexact_ui :: Ptr CFmpz -> Ptr CFmpz -> CULong -> IO ()

fmpz_divexact_ui f g h

Sets \(f\) to the quotient of \(g\) and \(h\), assuming that the division is exact, i.e.(g) is a multiple of \(h\). If \(h\) is \(0\) an exception is raised.

fmpz_divexact2_uiui :: Ptr CFmpz -> Ptr CFmpz -> CULong -> CULong -> IO ()

fmpz_divexact2_uiui f g x y

Sets \(f\) to the quotient of \(g\) and \(h = x \times y\), assuming that the division is exact, i.e.(g) is a multiple of \(h\). If \(x\) or \(y\) is \(0\) an exception is raised.

fmpz_divisible :: Ptr CFmpz -> Ptr CFmpz -> IO CInt

fmpz_divisible_si :: Ptr CFmpz -> CLong -> IO CInt

fmpz_divisible_si f g

Returns \(1\) if there is an integer \(q\) with \(f = q g\) and \(0\) if there is none.

fmpz_divides :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO CInt

fmpz_divides q g h

Returns \(1\) if there is an integer \(q\) with \(f = q g\) and sets \(q\) to the quotient. Otherwise returns \(0\) and sets \(q\) to \(0\).

fmpz_mod :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_mod f g h

Sets \(f\) to the remainder of \(g\) divided by \(h\) such that the remainder is positive. Assumes that \(h\) is not zero.

fmpz_mod_ui :: Ptr CFmpz -> Ptr CFmpz -> CULong -> IO CULong

fmpz_mod_ui f g h

Sets \(f\) to the remainder of \(g\) divided by \(h\) such that the remainder is positive and also returns this value. Raises an exception if \(h\) is zero.

fmpz_smod :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_smod f g h

Sets \(f\) to the signed remainder \(y \equiv g \bmod h\) satisfying \(-\lvert h \rvert/2 < y \leq \lvert h\rvert/2\).

fmpz_preinvn_init :: Ptr CFmpzPreInvN -> Ptr CFmpz -> IO ()

fmpz_preinvn_init inv f

Compute a precomputed inverse inv of f for use in the preinvn functions listed below.

fmpz_preinvn_clear :: Ptr CFmpzPreInvN -> IO ()

fmpz_preinvn_clear inv

Clean up the resources used by a precomputed inverse created with the fmpz_preinvn_init function.

fmpz_fdiv_qr_preinvn :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpzPreInvN -> IO ()

fmpz_fdiv_qr_preinvn f s g h hinv

As per fmpz_fdiv_qr, but takes a precomputed inverse hinv of \(h\) constructed using fmpz_preinvn.

This function will be faster than fmpz_fdiv_qr_preinvn when the number of limbs of \(h\) is at least PREINVN_CUTOFF.

fmpz_pow_ui :: Ptr CFmpz -> Ptr CFmpz -> CULong -> IO ()

fmpz_pow_ui f g x

Sets \(f\) to \(g^x\). Defines \(0^0 = 1\).

fmpz_pow_fmpz :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO CInt

fmpz_pow_fmpz f g x

Sets \(f\) to \(g^x\). Defines \(0^0 = 1\). Return \(1\) for success and \(0\) for failure. The function throws only if \(x\) is negative.

fmpz_powm_ui :: Ptr CFmpz -> Ptr CFmpz -> CULong -> Ptr CFmpz -> IO ()

fmpz_powm :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_powm f g e m

Sets \(f\) to \(g^e \bmod{m}\). If \(e = 0\), sets \(f\) to \(1\).

Assumes that \(m \neq 0\), raises an abort signal otherwise.

fmpz_clog :: Ptr CFmpz -> Ptr CFmpz -> IO CLong

fmpz_clog x b

Returns \(\lceil\log_b x\rceil\).

Assumes that \(x \geq 1\) and \(b \geq 2\) and that the return value fits into a signed slong.

fmpz_clog_ui :: Ptr CFmpz -> CULong -> IO CLong

fmpz_flog :: Ptr CFmpz -> Ptr CFmpz -> IO CLong

fmpz_flog x b

Returns \(\lfloor\log_b x\rfloor\).

Assumes that \(x \geq 1\) and \(b \geq 2\) and that the return value fits into a signed slong.

fmpz_dlog :: Ptr CFmpz -> IO CDouble

fmpz_dlog x

Returns a double precision approximation of the natural logarithm of \(x\).

The accuracy depends on the implementation of the floating-point logarithm provided by the C standard library. The result can typically be expected to have a relative error no greater than 1-2 bits.

fmpz_sqrtmod :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO CInt

fmpz_sqrtmod b a p

If \(p\) is prime, set \(b\) to a square root of \(a\) modulo \(p\) if \(a\) is a quadratic residue modulo \(p\) and return \(1\), otherwise return \(0\).

If \(p\) is not prime the return value is with high probability \(0\), indicating that \(p\) is not prime, or \(a\) is not a square modulo \(p\). If \(p\) is not prime and the return value is \(1\), the value of \(b\) is meaningless.

fmpz_sqrt :: Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_sqrt f g

Sets \(f\) to the integer part of the square root of \(g\), where \(g\) is assumed to be non-negative. If \(g\) is negative, an exception is raised.

fmpz_sqrtrem :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_sqrtrem f r g

Sets \(f\) to the integer part of the square root of \(g\), where \(g\) is assumed to be non-negative, and sets \(r\) to the remainder, that is, the difference \(g - f^2\). If \(g\) is negative, an exception is raised. The behaviour is undefined if \(f\) and \(r\) are aliases.

fmpz_is_square :: Ptr CFmpz -> IO CInt

fmpz_is_square f

Returns nonzero if \(f\) is a perfect square and zero otherwise.

fmpz_root :: Ptr CFmpz -> Ptr CFmpz -> CLong -> IO CInt

fmpz_root r f n

Set \(r\) to the integer part of the \(n\)-th root of \(f\). Requires that \(n > 0\) and that if \(n\) is even then \(f\) be non-negative, otherwise an exception is raised. The function returns \(1\) if the root was exact, otherwise \(0\).

fmpz_is_perfect_power :: Ptr CFmpz -> Ptr CFmpz -> IO CInt

fmpz_is_perfect_power root f

If \(f\) is a perfect power \(r^k\) set root to \(r\) and return \(k\), otherwise return \(0\). Note that \(-1, 0, 1\) are all considered perfect powers. No guarantee is made about \(r\) or \(k\) being the smallest possible value. Negative values of \(f\) are permitted.

fmpz_fac_ui :: Ptr CFmpz -> CULong -> IO ()

fmpz_fac_ui f n

Sets \(f\) to the factorial \(n!\) where \(n\) is an ulong.

fmpz_fib_ui :: Ptr CFmpz -> CULong -> IO ()

fmpz_fib_ui f n

Sets \(f\) to the Fibonacci number \(F_n\) where \(n\) is an ulong.

fmpz_bin_uiui :: Ptr CFmpz -> CULong -> CULong -> IO ()

fmpz_bin_uiui f n k

Sets \(f\) to the binomial coefficient \({n \choose k}\).

_fmpz_rfac_ui :: Ptr CFmpz -> Ptr CFmpz -> CULong -> CULong -> IO ()

_fmpz_rfac_ui r x a b

Sets \(r\) to the rising factorial \((x+a) (x+a+1) (x+a+2) \cdots (x+b-1)\). Assumes \(b > a\).

fmpz_rfac_ui :: Ptr CFmpz -> Ptr CFmpz -> CULong -> IO ()

fmpz_rfac_ui r x k

Sets \(r\) to the rising factorial \(x (x+1) (x+2) \cdots (x+k-1)\).

fmpz_rfac_uiui :: Ptr CFmpz -> CULong -> CULong -> IO ()

fmpz_rfac_uiui r x k

Sets \(r\) to the rising factorial \(x (x+1) (x+2) \cdots (x+k-1)\).

fmpz_mul_tdiv_q_2exp :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> CULong -> IO ()

fmpz_mul_tdiv_q_2exp f g h exp

Sets \(f\) to the product \(g\) and \(h\) divided by 2^exp, rounding down towards zero.

fmpz_mul_si_tdiv_q_2exp :: Ptr CFmpz -> Ptr CFmpz -> CLong -> CULong -> IO ()

fmpz_mul_si_tdiv_q_2exp f g x exp

Sets \(f\) to the product \(g\) and \(x\) divided by 2^exp, rounding down towards zero.

Greatest common divisor

fmpz_gcd_ui :: Ptr CFmpz -> Ptr CFmpz -> CULong -> IO ()

fmpz_gcd :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_gcd f g h

Sets \(f\) to the greatest common divisor of \(g\) and \(h\). The result is always positive, even if one of \(g\) and \(h\) is negative.

fmpz_gcd3 :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_gcd3 f a b c

Sets \(f\) to the greatest common divisor of \(a\), \(b\) and \(c\). This is equivalent to calling fmpz_gcd twice, but may be faster.

fmpz_lcm :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_lcm f g h

Sets \(f\) to the least common multiple of \(g\) and \(h\). The result is always nonnegative, even if one of \(g\) and \(h\) is negative.

fmpz_gcdinv :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_gcdinv d a f g

Given integers \(f, g\) with \(0 \leq f < g\), computes the greatest common divisor \(d = \gcd(f, g)\) and the modular inverse \(a = f^{-1} \pmod{g}\), whenever \(f \neq 0\).

Assumes that \(d\) and \(a\) are not aliased.

fmpz_xgcd :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_xgcd d a b f g

Computes the extended GCD of \(f\) and \(g\), i.e. the values \(a\) and \(b\) such that \(af + bg = d\), where \(d = \gcd(f, g)\). Here \(a\) will be the same as calling fmpz_gcdinv when \(f < g\) (or vice versa for \(b\) when \(g < f\)).

To obtain the canonical solution to Bézout's identity, call fmpz_xgcd_canonical_bezout instead. This is also faster.

Assumes that there is no aliasing among the outputs.

fmpz_xgcd_canonical_bezout :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_xgcd_canonical_bezout d a b f g

Computes the extended GCD \(\mathrm{xgcd}(f, g) = (d, a, b)\) such that the solution is the canonical solution to Bézout's identity. We define the canonical solution to satisfy one of the following if one of the given conditions apply:

\[\begin{aligned} \operatorname{xgcd}(\pm g, g) &= \bigl(|g|, 0, \operatorname{sgn}(g)\bigr)\\ \operatorname{xgcd}(f, 0) &= \bigl(|f|, \operatorname{sgn}(f), 0\bigr)\\ \operatorname{xgcd}(0, g) &= \bigl(|g|, 0, \operatorname{sgn}(g)\bigr)\\ \operatorname{xgcd}(f, \mp 1) &= (1, 0, \mp 1)\\ \operatorname{xgcd}(\mp 1, g) &= (1, \mp 1, 0)\quad g \neq 0, \pm 1\\ \operatorname{xgcd}(\mp 2 d, g) &= \bigl(d, {\textstyle\frac{d - |g|}{\mp 2 d}}, \operatorname{sgn}(g)\bigr)\\ \operatorname{xgcd}(f, \mp 2 d) &= \bigl(d, \operatorname{sgn}(f), {\textstyle\frac{d - |g|}{\mp 2 d}}\bigr). \end{aligned}\]

If the pair \((f, g)\) does not satisfy any of these conditions, the solution \((d, a, b)\) will satisfy the following:

\[`\] \[|a| < \Bigl| \frac{g}{2 d} \Bigr|, \qquad |b| < \Bigl| \frac{f}{2 d} \Bigr|.\]

Assumes that there is no aliasing among the outputs.

fmpz_xgcd_partial :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_xgcd_partial co2 co1 r2 r1 L

This function is an implementation of Lehmer extended GCD with early termination, as used in the qfb module. It terminates early when remainders fall below the specified bound. The initial values r1 and r2 are treated as successive remainders in the Euclidean algorithm and are replaced with the last two remainders computed. The values co1 and co2 are the last two cofactors and satisfy the identity co2*r1 - co1*r2 == +/- r2_orig upon termination, where r2_orig is the starting value of r2 supplied, and r1 and r2 are the final values.

Aliasing of inputs is not allowed. Similarly aliasing of inputs and outputs is not allowed.

Modular arithmetic

_fmpz_remove :: Ptr CFmpz -> Ptr CFmpz -> CDouble -> IO CLong

_fmpz_remove x f finv

Removes all factors \(f\) from \(x\) and returns the number of such.

Assumes that \(x\) is non-zero, that \(f > 1\) and that finv is the precomputed double inverse of \(f\) whenever \(f\) is a small integer and \(0\) otherwise.

Does not support aliasing.

fmpz_remove :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO CLong

fmpz_remove rop op f

Remove all occurrences of the factor \(f > 1\) from the integer op and sets rop to the resulting integer.

If op is zero, sets rop to op and returns \(0\).

Returns an abort signal if any of the assumptions are violated.

fmpz_invmod :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO CInt

fmpz_invmod f g h

Sets \(f\) to the inverse of \(g\) modulo \(h\). The value of \(h\) may not be \(0\) otherwise an exception results. If the inverse exists the return value will be non-zero, otherwise the return value will be \(0\) and the value of \(f\) undefined. As a special case, we consider any number invertible modulo \(h = \pm 1\), with inverse 0.

fmpz_negmod :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_negmod f g h

Sets \(f\) to \(-g \pmod{h}\), assuming \(g\) is reduced modulo \(h\).

fmpz_jacobi :: Ptr CFmpz -> Ptr CFmpz -> IO CInt

fmpz_jacobi a n

Computes the Jacobi symbol \(\left(\frac{a}{n}\right)\) for any \(a\) and odd positive \(n\).

fmpz_kronecker :: Ptr CFmpz -> Ptr CFmpz -> IO CInt

fmpz_kronecker a n

Computes the Kronecker symbol \(\left(\frac{a}{n}\right)\) for any \(a\) and any \(n\).

fmpz_divides_mod_list :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_divides_mod_list xstart xstride xlength a b n

Set \(xstart\), \(xstride\), and \(xlength\) so that the solution set for x modulo \(n\) in \(a x = b mod n\) is exactly \(\{xstart + xstride i | 0 \le i < xlength\}\). This function essentially gives a list of possibilities for the fraction \(a/b\) modulo \(n\). The outputs may not be aliased, and \(n\) should be positive.

Bit packing and unpacking

fmpz_bit_pack :: Ptr CMpLimb -> CFBitCnt -> CFBitCnt -> Ptr CFmpz -> CInt -> CInt -> IO CInt

fmpz_bit_pack arr shift bits coeff negate borrow

Shifts the given coefficient to the left by shift bits and adds it to the integer in arr in a field of the given number of bits:

shift  bits  --------------

X X X C C C C 0 0 0 0 0 0 0

An optional borrow of \(1\) can be subtracted from coeff before it is packed. If coeff is negative after the borrow, then a borrow will be returned by the function.

The value of shift is assumed to be less than FLINT_BITS. All but the first shift bits of arr are assumed to be zero on entry to the function.

The value of coeff may also be optionally (and notionally) negated before it is used, by setting the negate parameter to \(-1\).

fmpz_bit_unpack :: Ptr CFmpz -> Ptr CMpLimb -> CFBitCnt -> CFBitCnt -> CInt -> CInt -> IO CInt

fmpz_bit_unpack coeff arr shift bits negate borrow

A bit field of the given number of bits is extracted from arr, starting after shift bits, and placed into coeff. An optional borrow of \(1\) may be added to the coefficient. If the result is negative, a borrow of \(1\) is returned. Finally, the resulting coeff may be negated by setting the negate parameter to \(-1\).

The value of shift is expected to be less than FLINT_BITS.

fmpz_bit_unpack_unsigned :: Ptr CFmpz -> Ptr CMpLimb -> CFBitCnt -> CFBitCnt -> IO ()

fmpz_bit_unpack_unsigned coeff arr shift bits

A bit field of the given number of bits is extracted from arr, starting after shift bits, and placed into coeff.

The value of shift is expected to be less than FLINT_BITS.

Logic Operations

fmpz_complement :: Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_complement r f

The variable r is set to the ones-complement of f.

fmpz_clrbit :: Ptr CFmpz -> CULong -> IO ()

fmpz_clrbit f i

Sets the ith bit in f to zero.

fmpz_combit :: Ptr CFmpz -> CULong -> IO ()

fmpz_combit f i

Complements the ith bit in f.

fmpz_and :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_and r a b

Sets r to the bit-wise logical and of a and b.

fmpz_or :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_or r a b

Sets r to the bit-wise logical (inclusive) or of a and b.

fmpz_xor :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_xor r a b

Sets r to the bit-wise logical exclusive or of a and b.

fmpz_popcnt :: Ptr CFmpz -> IO CInt

fmpz_popcnt a

Returns the number of '1' bits in the given Z (aka Hamming weight or population count). The return value is undefined if the input is negative.

Chinese remaindering

fmpz_CRT_ui :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> CULong -> CULong -> CInt -> IO ()

fmpz_CRT_ui out r1 m1 r2 m2 sign

Uses the Chinese Remainder Theorem to compute the unique integer \(0 \le x < M\) (if sign = 0) or \(-M/2 < x \le M/2\) (if sign = 1) congruent to \(r_1\) modulo \(m_1\) and \(r_2\) modulo \(m_2\), where where \(M = m_1 \times m_2\). The result \(x\) is stored in out.

It is assumed that \(m_1\) and \(m_2\) are positive integers greater than \(1\) and coprime.

If sign = 0, it is assumed that \(0 \le r_1 < m_1\) and \(0 \le r_2 < m_2\). Otherwise, it is assumed that \(-m_1 \le r_1 < m_1\) and \(0 \le r_2 < m_2\).

fmpz_CRT :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> CInt -> IO ()

fmpz_CRT out r1 m1 r2 m2 sign

Use the Chinese Remainder Theorem to set out to the unique value \(0 \le x < M\) (if sign = 0) or \(-M/2 < x \le M/2\) (if sign = 1) congruent to \(r_1\) modulo \(m_1\) and \(r_2\) modulo \(m_2\), where where \(M = m_1 \times m_2\).

It is assumed that \(m_1\) and \(m_2\) are positive integers greater than \(1\) and coprime.

If sign = 0, it is assumed that \(0 \le r_1 < m_1\) and \(0 \le r_2 < m_2\). Otherwise, it is assumed that \(-m_1 \le r_1 < m_1\) and \(0 \le r_2 < m_2\).

fmpz_multi_mod_ui :: Ptr CMpLimb -> Ptr CFmpz -> Ptr CFmpzComb -> Ptr CFmpzCombTemp -> IO ()

fmpz_multi_mod_ui out in comb temp

Reduces the multiprecision integer in modulo each of the primes stored in the comb structure. The array out will be filled with the residues modulo these primes. The structure temp is temporary space which must be provided by fmpz_comb_temp_init and cleared by fmpz_comb_temp_clear.

fmpz_multi_CRT_ui :: Ptr CFmpz -> Ptr CMp -> Ptr CFmpzComb -> Ptr CFmpzCombTemp -> CInt -> IO ()

fmpz_multi_CRT_ui output residues comb ctemp sign

This function takes a set of residues modulo the list of primes contained in the comb structure and reconstructs a multiprecision integer modulo the product of the primes which has these residues modulo the corresponding primes.

If \(N\) is the product of all the primes then out is normalised to be in the range \([0, N)\) if sign = 0 and the range \([-(N-1)/2, N/2]\) if sign = 1. The array temp is temporary space which must be provided by fmpz_comb_temp_init and cleared by fmpz_comb_temp_clear.

Comb for multi CRT

data FmpzComb

Data structure containing CFmpzComb pointer

Constructors

FmpzComb !(ForeignPtr CFmpzComb)

Instances

Storable CFmpzComb

Defined in Data.Number.Flint.Fmpz.FFI

Methods

sizeOf :: CFmpzComb -> Int

alignment :: CFmpzComb -> Int

peekElemOff :: Ptr CFmpzComb -> Int -> IO CFmpzComb

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

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

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

peek :: Ptr CFmpzComb -> IO CFmpzComb

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

type CFmpzComb = CFlint FmpzComb

data FmpzCombTemp

Data structure containing CFmpzCombTemp pointer

Constructors

FmpzCombTemp !(ForeignPtr CFmpzCombTemp)

Instances

Storable CFmpzCombTemp

Defined in Data.Number.Flint.Fmpz.FFI

Methods

sizeOf :: CFmpzCombTemp -> Int

alignment :: CFmpzCombTemp -> Int

peekElemOff :: Ptr CFmpzCombTemp -> Int -> IO CFmpzCombTemp

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

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

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

peek :: Ptr CFmpzCombTemp -> IO CFmpzCombTemp

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

type CFmpzCombTemp = CFlint FmpzCombTemp

newFmpzComb :: Ptr CMp -> CLong -> IO FmpzComb

withFmpzComb :: FmpzComb -> (Ptr CFmpzComb -> IO a) -> IO (FmpzComb, a)

fmpz_comb_init :: Ptr CFmpzComb -> Ptr CMp -> CLong -> IO ()

fmpz_comb_init comb primes num_primes

Initialises a comb structure for multimodular reduction and recombination. The array primes is assumed to contain num_primes primes each of FLINT_BITS - 1 bits. Modular reductions and recombinations will be done modulo this list of primes. The primes array must not be free'd until the comb structure is no longer required and must be cleared by the user.

newFmpzCombTemp :: Ptr CFmpzComb -> IO FmpzCombTemp

withFmpzCombTemp :: FmpzCombTemp -> (Ptr CFmpzCombTemp -> IO a) -> IO (FmpzCombTemp, a)

fmpz_comb_temp_init :: Ptr CFmpzCombTemp -> Ptr CFmpzComb -> IO ()

fmpz_comb_temp_init temp comb

Creates temporary space to be used by multimodular and CRT functions based on an initialised comb structure.

fmpz_comb_clear :: Ptr CFmpzComb -> IO ()

fmpz_comb_clear comb

Clears the given comb structure, releasing any memory it uses.

fmpz_comb_temp_clear :: Ptr CFmpzCombTemp -> IO ()

fmpz_comb_temp_clear temp

Clears temporary space temp used by multimodular and CRT functions using the given comb structure.

Multi CRT

data FmpzMultiCRT

Data structure containing CFmpzMultiCRT pointer

Constructors

FmpzMultiCRT !(ForeignPtr CFmpzMultiCRT)

Instances

Storable CFmpzMultiCRT

Defined in Data.Number.Flint.Fmpz.FFI

Methods

sizeOf :: CFmpzMultiCRT -> Int

alignment :: CFmpzMultiCRT -> Int

peekElemOff :: Ptr CFmpzMultiCRT -> Int -> IO CFmpzMultiCRT

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

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

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

peek :: Ptr CFmpzMultiCRT -> IO CFmpzMultiCRT

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

type CFmpzMultiCRT = CFlint FmpzMultiCRT

newFmpzMultiCRT :: IO FmpzMultiCRT

withFmpzMultiCRT :: FmpzMultiCRT -> (Ptr CFmpzMultiCRT -> IO a) -> IO (FmpzMultiCRT, a)

fmpz_multi_CRT_init :: Ptr CFmpzMultiCRT -> IO ()

fmpz_multi_CRT_init CRT

Initialize CRT for Chinese remaindering.

fmpz_multi_CRT_precompute :: Ptr CFmpzMultiCRT -> Ptr CFmpz -> CLong -> IO CInt

fmpz_multi_CRT_precompute CRT moduli len

Configure CRT for repeated Chinese remaindering of moduli. The number of moduli, len, should be positive. A return of 0 indicates that the compilation failed and future calls to fmpz_crt_precomp will leave the output undefined. A return of 1 indicates that the compilation was successful, which occurs if and only if either (1) len == 1 and modulus + 0 is nonzero, or (2) no modulus is \(0,1,-1\) and all moduli are pairwise relatively prime.

fmpz_multi_CRT_precomp :: Ptr CFmpz -> Ptr CFmpzMultiCRT -> Ptr CFmpz -> IO ()

fmpz_multi_CRT_precomp output P inputs

Set output to an integer of smallest absolute value that is congruent to values + i modulo the moduli + i in fmpz_crt_precompute.

fmpz_multi_CRT :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> CLong -> IO CInt

fmpz_multi_CRT output moduli values len

Perform the same operation as fmpz_multi_CRT_precomp while internally constructing and destroying the precomputed data. All of the remarks in fmpz_multi_CRT_precompute apply.

fmpz_multi_CRT_clear :: Ptr CFmpzMultiCRT -> IO ()

fmpz_multi_CRT_clear P

Free all space used by CRT.

Primality testing

fmpz_is_strong_probabprime :: Ptr CFmpz -> Ptr CFmpz -> IO CInt

fmpz_is_strong_probabprime n a

Returns \(1\) if \(n\) is a strong probable prime to base \(a\), otherwise it returns \(0\).

fmpz_is_probabprime_lucas :: Ptr CFmpz -> IO CInt

fmpz_is_probabprime_lucas n

Performs a Lucas probable prime test with parameters chosen by Selfridge's method \(A\) as per [BaiWag1980].

Return \(1\) if \(n\) is a Lucas probable prime, otherwise return \(0\). This function declares some composites probably prime, but no primes composite.

fmpz_is_probabprime_BPSW :: Ptr CFmpz -> IO CInt

fmpz_is_probabprime_BPSW n

Perform a Baillie-PSW probable prime test with parameters chosen by Selfridge's method \(A\) as per [BaiWag1980].

Return \(1\) if \(n\) is a Lucas probable prime, otherwise return \(0\).

There are no known composites passed as prime by this test, though infinitely many probably exist. The test will declare no primes composite.

fmpz_is_probabprime :: Ptr CFmpz -> IO CInt

fmpz_is_probabprime p

Performs some trial division and then some probabilistic primality tests. If \(p\) is definitely composite, the function returns \(0\), otherwise it is declared probably prime, i.e. prime for most practical purposes, and the function returns \(1\). The chance of declaring a composite prime is very small.

Subsequent calls to the same function do not increase the probability of the number being prime.

fmpz_is_prime_pseudosquare :: Ptr CFmpz -> IO CInt

fmpz_is_prime_pseudosquare n

Return \(0\) is \(n\) is composite. If \(n\) is too large (greater than about \(94\) bits) the function fails silently and returns \(-1\), otherwise, if \(n\) is proven prime by the pseudosquares method, return \(1\).

Tests if \(n\) is a prime according to [Theorem 2.7] [LukPatWil1996].

We first factor \(N\) using trial division up to some limit \(B\). In fact, the number of primes used in the trial factoring is at most FLINT_PSEUDOSQUARES_CUTOFF.

Next we compute \(N/B\) and find the next pseudosquare \(L_p\) above this value, using a static table as per https://oeis.org/A002189/b002189.txt.

As noted in the text, if \(p\) is prime then Step 3 will pass. This test rejects many composites, and so by this time we suspect that \(p\) is prime. If \(N\) is \(3\) or \(7\) modulo \(8\), we are done, and \(N\) is prime.

We now run a probable prime test, for which no known counterexamples are known, to reject any composites. We then proceed to prove \(N\) prime by executing Step 4. In the case that \(N\) is \(1\) modulo \(8\), if Step 4 fails, we extend the number of primes \(p_i\) at Step 3 and hope to find one which passes Step 4. We take the test one past the largest \(p\) for which we have pseudosquares \(L_p\) tabulated, as this already corresponds to the next \(L_p\) which is bigger than \(2^{64}\) and hence larger than any prime we might be testing.

As explained in the text, Condition 4 cannot fail if \(N\) is prime.

The possibility exists that the probable prime test declares a composite prime. However in that case an error is printed, as that would be of independent interest.

fmpz_is_prime_pocklington :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CMp -> CLong -> IO CInt

fmpz_is_prime_pocklington F R n pm1 num_pm1

Applies the Pocklington primality test. The test computes a product \(F\) of prime powers which divide \(n - 1\).

The function then returns either \(0\) if \(n\) is definitely composite or it returns \(1\) if all factors of \(n\) are \(1 \pmod{F}\). Also in that case, \(R\) is set to \((n - 1)/F\).

N.B: a return value of \(1\) only proves \(n\) prime if \(F \ge \sqrt{n}\).

The function does not compute which primes divide \(n - 1\). Instead, these must be supplied as an array pm1 of length num_pm1. It does not matter how many prime factors are supplied, but the more that are supplied, the larger F will be.

There is a balance between the amount of time spent looking for factors of \(n - 1\) and the usefulness of the output (F may be as low as \(2\) in some cases).

A reasonable heuristic seems to be to choose limit to be some small multiple of \(\log^3(n)/10\) (e.g. \(1, 2, 5\) or \(10\)) depending on how long one is prepared to wait, then to trial factor up to the limit. (See _fmpz_nm1_trial_factors.)

Requires \(n\) to be odd.

_fmpz_nm1_trial_factors :: Ptr CFmpz -> Ptr CMp -> Ptr CLong -> CULong -> IO ()

_fmpz_nm1_trial_factors n pm1 num_pm1 limit

Trial factors \(n - 1\) up to the given limit (approximately) and stores the factors in an array pm1 whose length is written out to num_pm1.

One can use \(\log(n) + 2\) as a bound on the number of factors which might be produced (and hence on the length of the array that needs to be supplied).

fmpz_is_prime_morrison :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CMp -> CLong -> IO CInt

fmpz_is_prime_morrison F R n pp1 num_pp1

Applies the Morrison \(p + 1\) primality test. The test computes a product \(F\) of primes which divide \(n + 1\).

The function then returns either \(0\) if \(n\) is definitely composite or it returns \(1\) if all factors of \(n\) are \(\pm 1 \pmod{F}\). Also in that case, \(R\) is set to \((n + 1)/F\).

N.B: a return value of \(1\) only proves \(n\) prime if \(F > \sqrt{n} + 1\).

The function does not compute which primes divide \(n + 1\). Instead, these must be supplied as an array pp1 of length num_pp1. It does not matter how many prime factors are supplied, but the more that are supplied, the larger \(F\) will be.

There is a balance between the amount of time spent looking for factors of \(n + 1\) and the usefulness of the output (F may be as low as \(2\) in some cases).

A reasonable heuristic seems to be to choose limit to be some small multiple of \(\log^3(n)/10\) (e.g. \(1, 2, 5\) or \(10\)) depending on how long one is prepared to wait, then to trial factor up to the limit. (See _fmpz_np1_trial_factors.)

Requires \(n\) to be odd and non-square.

_fmpz_np1_trial_factors :: Ptr CFmpz -> Ptr CMp -> Ptr CLong -> CULong -> IO ()

_fmpz_np1_trial_factors n pp1 num_pp1 limit

Trial factors \(n + 1\) up to the given limit (approximately) and stores the factors in an array pp1 whose length is written out to num_pp1.

One can use \(\log(n) + 2\) as a bound on the number of factors which might be produced (and hence on the length of the array that needs to be supplied).

fmpz_is_prime :: Ptr CFmpz -> IO CInt

fmpz_is_prime n

Attempts to prove \(n\) prime. If \(n\) is proven prime, the function returns \(1\). If \(n\) is definitely composite, the function returns \(0\).

This function calls n_is_prime for \(n\) that fits in a single word. For \(n\) larger than one word, it tests divisibility by a few small primes and whether \(n\) is a perfect square to rule out trivial composites. For \(n\) up to about 81 bits, it then uses a strong probable prime test (Miller-Rabin test) with the first 13 primes as witnesses. This has been shown to prove primality [SorWeb2016].

For larger \(n\), it does a single base-2 strong probable prime test to eliminate most composite numbers. If \(n\) passes, it does a combination of Pocklington, Morrison and Brillhart, Lehmer, Selfridge tests. If any of these tests fails to give a proof, it falls back to performing an APRCL test.

The APRCL test could theoretically fail to prove that \(n\) is prime or composite. In that case, the program aborts. This is not expected to occur in practice.

fmpz_lucas_chain :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_lucas_chain Vm Vm1 A m n

Given \(V_0 = 2\), \(V_1 = A\) compute \(V_m, V_{m + 1} \pmod{n}\) from the recurrences \(V_j = AV_{j - 1} - V_{j - 2} \pmod{n}\).

This is computed efficiently using \(V_{2j} = V_j^2 - 2 \pmod{n}\) and \(V_{2j + 1} = V_jV_{j + 1} - A \pmod{n}\).

No aliasing is permitted.

fmpz_lucas_chain_full :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_lucas_chain_full Vm Vm1 A B m n

Given \(V_0 = 2\), \(V_1 = A\) compute \(V_m, V_{m + 1} \pmod{n}\) from the recurrences \(V_j = AV_{j - 1} - BV_{j - 2} \pmod{n}\).

This is computed efficiently using double and add formulas.

No aliasing is permitted.

fmpz_lucas_chain_double :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_lucas_chain_double U2m U2m1 Um Um1 A B n

Given \(U_m, U_{m + 1} \pmod{n}\) compute \(U_{2m}, U_{2m + 1} \pmod{n}\).

Aliasing of \(U_{2m}\) and \(U_m\) and aliasing of \(U_{2m + 1}\) and \(U_{m + 1}\) is permitted. No other aliasing is allowed.

fmpz_lucas_chain_add :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_lucas_chain_add Umn Umn1 Um Um1 Un Un1 A B n

Given \(U_m, U_{m + 1} \pmod{n}\) and \(U_n, U_{n + 1} \pmod{n}\) compute \(U_{m + n}, U_{m + n + 1} \pmod{n}\).

Aliasing of \(U_{m + n}\) with \(U_m\) or \(U_n\) and aliasing of \(U_{m + n + 1}\) with \(U_{m + 1}\) or \(U_{n + 1}\) is permitted. No other aliasing is allowed.

fmpz_lucas_chain_mul :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_lucas_chain_mul Ukm Ukm1 Um Um1 A B k n

Given \(U_m, U_{m + 1} \pmod{n}\) compute \(U_{km}, U_{km + 1} \pmod{n}\).

Aliasing of \(U_{km}\) and \(U_m\) and aliasing of \(U_{km + 1}\) and \(U_{m + 1}\) is permitted. No other aliasing is allowed.

fmpz_lucas_chain_VtoU :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_lucas_chain_VtoU Um Um1 Vm Vm1 A B Dinv n

Given \(V_m, V_{m + 1} \pmod{n}\) compute \(U_m, U_{m + 1} \pmod{n}\).

Aliasing of \(V_m\) and \(U_m\) and aliasing of \(V_{m + 1}\) and \(U_{m + 1}\) is permitted. No other aliasing is allowed.

fmpz_divisor_in_residue_class_lenstra :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO CInt

fmpz_divisor_in_residue_class_lenstra fac n r s

If there exists a proper divisor of \(n\) which is \(r \pmod{s}\) for \(0 < r < s < n\), this function returns \(1\) and sets fac to such a divisor. Otherwise the function returns \(0\) and the value of fac is undefined.

We require \(\gcd(r, s) = 1\).

This is efficient if \(s^3 > n\).

fmpz_nextprime :: Ptr CFmpz -> Ptr CFmpz -> CInt -> IO ()

fmpz_nextprime res n proved

Finds the next prime number larger than \(n\).

If proved is nonzero, then the integer returned is guaranteed to actually be prime. Otherwise if \(n\) fits in FLINT_BITS - 3 bits n_nextprime is called, and if not then the GMP mpz_nextprime function is called. Up to an including GMP 6.1.2 this used Miller-Rabin iterations, and thereafter uses a BPSW test.

Special functions

fmpz_primorial :: Ptr CFmpz -> CULong -> IO ()

fmpz_primorial res n

Sets res to n primorial or \(n \#\), the product of all prime numbers less than or equal to \(n\).

fmpz_factor_euler_phi :: Ptr CFmpz -> Ptr CFmpzFactor -> IO ()

fmpz_factor_euler_phi res fac

Sets res to the Euler totient function \(\phi(n)\), counting the number of positive integers less than or equal to \(n\) that are coprime to \(n\). The factor version takes a precomputed factorisation of \(n\).

fmpz_euler_phi :: Ptr CFmpz -> Ptr CFmpz -> IO ()

fmpz_factor_moebius_mu :: Ptr CFmpzFactor -> IO CInt

fmpz_factor_moebius_mu fac

Computes the Moebius function \(\mu(n)\), which is defined as \(\mu(n) = 0\) if \(n\) has a prime factor of multiplicity greater than \(1\), \(\mu(n) = -1\) if \(n\) has an odd number of distinct prime factors, and \(\mu(n) = 1\) if \(n\) has an even number of distinct prime factors. By convention, \(\mu(0) = 0\). The factor version takes a precomputed factorisation of \(n\).

fmpz_moebius_mu :: Ptr CFmpz -> Ptr CFmpz -> CInt

fmpz_factor_divisor_sigma :: Ptr CFmpz -> CULong -> Ptr CFmpzFactor -> IO ()

fmpz_factor_divisor_sigma res k fac

Sets res to \(\sigma_k(n)\), the sum of (k`th powers of all divisors of :math:`n). The factor version takes a precomputed factorisation of \(n\).

fmpz_divisor_sigma :: Ptr CFmpz -> CULong -> Ptr CFmpz -> IO ()