Data.Number.Flint.APRCL

APRCL primality testing

data APRCLConfig

Constructors

Gauss !(ForeignPtr CAPRCLConfig)

Jacobi !(ForeignPtr CAPRCLConfig)

data CAPRCLConfig

Constructors

CAPRCLConfig CULong (Ptr CFmpz) (Ptr CNFactor) (Ptr CFmpz) (Ptr CInt)

Instances

Storable CAPRCLConfig

Defined in Data.Number.Flint.APRCL.FFI

Methods

sizeOf :: CAPRCLConfig -> Int

alignment :: CAPRCLConfig -> Int

peekElemOff :: Ptr CAPRCLConfig -> Int -> IO CAPRCLConfig

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

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

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

peek :: Ptr CAPRCLConfig -> IO CAPRCLConfig

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

newAPRCLConfigGauss :: Fmpz -> IO APRCLConfig

newAPRCLConfigJacobi :: Fmpz -> IO APRCLConfig

withAPRCLConfig :: APRCLConfig -> (Ptr CAPRCLConfig -> IO a) -> IO (APRCLConfig, a)

Primality test functions

aprcl_is_prime :: Ptr CFmpz -> IO CInt

aprcl_is_prime n

Tests \(n\) for primality using the APRCL test. This is the same as aprcl_is_prime_jacobi.

aprcl_is_prime_jacobi :: Ptr CFmpz -> IO CInt

aprcl_is_prime_jacobi n

If \(n\) is prime returns 1; otherwise returns 0. The algorithm is well described in "Implementation of a New Primality Test" by H. Cohen and A.K. Lenstra and "A Course in Computational Algebraic Number Theory" by H. Cohen.

It is theoretically possible that this function fails to prove that \(n\) is prime. In this event, flint_abort is called. To handle this condition, the _aprcl_is_prime_jacobi function can be used.

aprcl_is_prime_gauss :: Ptr CFmpz -> IO CInt

aprcl_is_prime_gauss n

If \(n\) is prime returns 1; otherwise returns 0. Uses the cyclotomic primality testing algorithm described in "Four primality testing algorithms" by Rene Schoof. The minimum required numbers \(s\) and \(R\) are computed automatically.

By default \(R \ge 180\). In some cases this function fails to prove that \(n\) is prime. This means that we select a too small \(R\) value. In this event, flint_abort is called. To handle this condition, the _aprcl_is_prime_jacobi function can be used.

_aprcl_is_prime_jacobi :: Ptr CFmpz -> Ptr CAPRCLConfig -> IO PrimalityTestStatus

_aprcl_is_prime_jacobi n config

Jacobi sum test for \(n\). Possible return values: PRIME, COMPOSITE and UNKNOWN (if we cannot prove primality).

_aprcl_is_prime_gauss :: Ptr CFmpz -> Ptr CAPRCLConfig -> IO PrimalityTestStatus

_aprcl_is_prime_gauss n config

Tests \(n\) for primality with fixed config. Possible return values: PRIME, COMPOSITE and PROBABPRIME (if we cannot prove primality).

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

aprcl_is_prime_gauss_min_R n R

Same as aprcl_is_prime_gauss with fixed minimum value of \(R\).

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

aprcl_is_prime_final_division n s r

Returns 0 if for some \(a = n^k \bmod s\), where \(k \in [1, r - 1]\), we have that \(a \mid n\); otherwise returns 1.

Configuration functions

aprcl_config_gauss_init :: Ptr CAPRCLConfig -> Ptr CFmpz -> IO ()

aprcl_config_gauss_init conf n

Computes the \(s\) and \(R\) values used in the cyclotomic primality test, \(s^2 > n\) and \(s=\prod\limits_{\substack{q-1\mid R \\ q \text{ prime}}}q\). Also stores factors of \(R\) and \(s\).

aprcl_config_gauss_init_min_R :: Ptr CAPRCLConfig -> Ptr CFmpz -> CULong -> IO ()

aprcl_config_gauss_init_min_R conf n R

Computes the \(s\) with fixed minimum \(R\) such that \(a^R \equiv 1 \mod{s}\) for all integers \(a\) coprime to \(s\).

aprcl_config_gauss_clear :: Ptr CAPRCLConfig -> IO ()

aprcl_config_gauss_clear conf

Clears the given aprcl_config element. It must be reinitialised in order to be used again.

aprcl_R_value :: Ptr CFmpz -> IO CULong

aprcl_R_value n

Returns a precomputed \(R\) value for APRCL, such that the corresponding \(s\) value is greater than \(\sqrt{n}\). The maximum stored value \(6983776800\) allows to test numbers up to \(6000\) digits.

aprcl_config_jacobi_init :: Ptr CAPRCLConfig -> Ptr CFmpz -> IO ()

aprcl_config_jacobi_init conf n

Computes the \(s\) and \(R\) values used in the cyclotomic primality test, \(s^2 > n\) and \(a^R \equiv 1 \mod{s}\) for all \(a\) coprime to \(s\). Also stores factors of \(R\) and \(s\).

aprcl_config_jacobi_clear :: Ptr CAPRCLConfig -> IO ()

aprcl_config_jacobi_clear conf

Clears the given aprcl_config element. It must be reinitialised in order to be used again.

Cyclotomic arithmetic

data UnityZp

Constructors

UnityZp !(ForeignPtr CUnityZp)

data CUnityZp

Constructors

CUnityZp (Ptr CFmpzModPoly) CULong CULong (Ptr CFmpzModCtx)

Instances

Storable CUnityZp

Defined in Data.Number.Flint.APRCL.FFI

Methods

sizeOf :: CUnityZp -> Int

alignment :: CUnityZp -> Int

peekElemOff :: Ptr CUnityZp -> Int -> IO CUnityZp

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

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

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

peek :: Ptr CUnityZp -> IO CUnityZp

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

newUnityZp :: CULong -> CULong -> Fmpz -> IO UnityZp

withUnityZp :: UnityZp -> (Ptr CUnityZp -> IO a) -> IO (UnityZp, a)

data UnityZpq

Constructors

UnityZpq !(ForeignPtr CUnityZpq)

Instances

Storable CUnityZpq

Defined in Data.Number.Flint.APRCL.FFI

Methods

sizeOf :: CUnityZpq -> Int

alignment :: CUnityZpq -> Int

peekElemOff :: Ptr CUnityZpq -> Int -> IO CUnityZpq

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

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

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

peek :: Ptr CUnityZpq -> IO CUnityZpq

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

type CUnityZpq = CFlint UnityZpq

newUnityZpq :: CULong -> CULong -> Fmpz -> IO UnityZpq

withUnityZpq :: UnityZpq -> (Ptr CUnityZpq -> IO a) -> IO (UnityZpq, a)

Memory management

unity_zp_init :: Ptr CUnityZp -> CULong -> CULong -> Ptr CFmpz -> IO ()

unity_zp_init f p exp n

Initializes \(f\) as an element of \(\mathbb{Z}[\zeta_{p^{exp}}]/(n)\).

unity_zp_clear :: Ptr CUnityZp -> IO ()

unity_zp_clear f

Clears the given element. It must be reinitialised in order to be used again.

unity_zp_copy :: Ptr CUnityZp -> Ptr CUnityZp -> IO ()

unity_zp_copy f g

Sets \(f\) to \(g\). \(f\) and \(g\) must be initialized with same \(p\) and \(n\).

unity_zp_swap :: Ptr CUnityZp -> Ptr CUnityZp -> IO ()

unity_zp_swap f q

Swaps \(f\) and \(g\). \(f\) and \(g\) must be initialized with same \(p\) and \(n\).

unity_zp_set_zero :: Ptr CUnityZp -> IO ()

unity_zp_set_zero f

Sets \(f\) to zero.

Comparison

unity_zp_is_unity :: Ptr CUnityZp -> IO CLong

unity_zp_is_unity f

If \(f = \zeta^h\) returns h; otherwise returns -1.

unity_zp_equal :: Ptr CUnityZp -> Ptr CUnityZp -> IO CInt

unity_zp_equal f g

Returns nonzero if \(f = g\) reduced by the \(p^{exp}\)-th cyclotomic polynomial.

Output

unity_zp_print :: Ptr CUnityZp -> IO ()

unity_zp_print f

Prints the contents of the \(f\).

Coefficient management

unity_zp_coeff_set_fmpz :: Ptr CUnityZp -> CULong -> Ptr CFmpz -> IO ()

unity_zp_coeff_set_fmpz f ind x

unity_zp_coeff_set_ui :: Ptr CUnityZp -> CULong -> CULong -> IO ()

unity_zp_coeff_set_ui f ind x

Sets the coefficient of \(\zeta^{ind}\) to \(x\). \(ind\) must be less than \(p^{exp}\).

unity_zp_coeff_add_fmpz :: Ptr CUnityZp -> CULong -> Ptr CFmpz -> IO ()

unity_zp_coeff_add_fmpz f ind x

unity_zp_coeff_add_ui :: Ptr CUnityZp -> CULong -> CULong -> IO ()

unity_zp_coeff_add_ui f ind x

Adds \(x\) to the coefficient of \(\zeta^{ind}\). \(x\) must be less than \(n\). \(ind\) must be less than \(p^{exp}\).

unity_zp_coeff_inc :: Ptr CUnityZp -> CULong -> IO ()

unity_zp_coeff_inc f ind

Increments the coefficient of \(\zeta^{ind}\). \(ind\) must be less than \(p^{exp}\).

unity_zp_coeff_dec :: Ptr CUnityZp -> CULong -> IO ()

unity_zp_coeff_dec f ind

Decrements the coefficient of \(\zeta^{ind}\). \(ind\) must be less than \(p^{exp}\).

Scalar multiplication

unity_zp_mul_scalar_fmpz :: Ptr CUnityZp -> Ptr CUnityZp -> Ptr CFmpz -> IO ()

unity_zp_mul_scalar_fmpz f g s

Sets \(f\) to \(s \cdot g\). \(f\) and \(g\) must be initialized with same \(p\), \(exp\) and \(n\).

unity_zp_mul_scalar_ui :: Ptr CUnityZp -> Ptr CUnityZp -> CULong -> IO ()

unity_zp_mul_scalar_ui f g s

Sets \(f\) to \(s \cdot g\). \(f\) and \(g\) must be initialized with same \(p\), \(exp\) and \(n\).

Addition and multiplication

unity_zp_add :: Ptr CUnityZp -> Ptr CUnityZp -> Ptr CUnityZp -> IO ()

unity_zp_add f g h

Sets \(f\) to \(g + h\). \(f\), \(g\) and \(h\) must be initialized with same \(p\), \(exp\) and \(n\).

unity_zp_mul :: Ptr CUnityZp -> Ptr CUnityZp -> Ptr CUnityZp -> IO ()

unity_zp_mul f g h

Sets \(f\) to \(g \cdot h\). \(f\), \(g\) and \(h\) must be initialized with same \(p\), \(exp\) and \(n\).

unity_zp_sqr :: Ptr CUnityZp -> Ptr CUnityZp -> IO ()

unity_zp_sqr f g

Sets \(f\) to \(g \cdot g\). \(f\), \(g\) and \(h\) must be initialized with same \(p\), \(exp\) and \(n\).

unity_zp_mul_inplace :: Ptr CUnityZp -> Ptr CUnityZp -> Ptr CUnityZp -> Ptr (Ptr CFmpz) -> IO ()

unity_zp_mul_inplace f g h t

Sets \(f\) to \(g \cdot h\). If \(p^{exp} = 3, 4, 5, 7, 8, 9, 11, 16\) special multiplication functions are used. The preallocated array \(t\) of fmpz_t is used for all computations in this case. \(f\), \(g\) and \(h\) must be initialized with same \(p\), \(exp\) and \(n\).

unity_zp_sqr_inplace :: Ptr CUnityZp -> Ptr CUnityZp -> Ptr (Ptr CFmpz) -> IO ()

unity_zp_sqr_inplace f g t

Sets \(f\) to \(g \cdot g\). If \(p^{exp} = 3, 4, 5, 7, 8, 9, 11, 16\) special multiplication functions are used. The preallocated array \(t\) of fmpz_t is used for all computations in this case. \(f\) and \(g\) must be initialized with same \(p\), \(exp\) and \(n\).

Powering functions

unity_zp_pow_fmpz :: Ptr CUnityZp -> Ptr CUnityZp -> Ptr CFmpz -> IO ()

unity_zp_pow_fmpz f g pow

Sets \(f\) to \(g^{pow}\). \(f\) and \(g\) must be initialized with same \(p\), \(exp\) and \(n\).

unity_zp_pow_ui :: Ptr CUnityZp -> Ptr CUnityZp -> CULong -> IO ()

unity_zp_pow_ui f g pow

Sets \(f\) to \(g^{pow}\). \(f\) and \(g\) must be initialized with same \(p\), \(exp\) and \(n\).

_unity_zp_pow_select_k :: Ptr CFmpz -> IO CULong

_unity_zp_pow_select_k n

Returns the smallest integer \(k\) satisfying \(\log (n) < (k(k + 1)2^{2k}) / (2^{k + 1} - k - 2) + 1\)

unity_zp_pow_2k_fmpz :: Ptr CUnityZp -> Ptr CUnityZp -> Ptr CFmpz -> IO ()

unity_zp_pow_2k_fmpz f g pow

Sets \(f\) to \(g^{pow}\) using the \(2^k\)-ary exponentiation method. \(f\) and \(g\) must be initialized with same \(p\), \(exp\) and \(n\).

unity_zp_pow_2k_ui :: Ptr CUnityZp -> Ptr CUnityZp -> CULong -> IO ()

unity_zp_pow_2k_ui f g pow

Sets \(f\) to \(g^{pow}\) using the \(2^k\)-ary exponentiation method. \(f\) and \(g\) must be initialized with same \(p\), \(exp\) and \(n\).

unity_zp_pow_sliding_fmpz :: Ptr CUnityZp -> Ptr CUnityZp -> Ptr CFmpz -> IO ()

unity_zp_pow_sliding_fmpz f g pow

Sets \(f\) to \(g^{pow}\) using the sliding window exponentiation method. \(f\) and \(g\) must be initialized with same \(p\), \(exp\) and \(n\).

Cyclotomic reduction

_unity_zp_reduce_cyclotomic_divmod :: Ptr CUnityZp -> IO ()

_unity_zp_reduce_cyclotomic_divmod f

_unity_zp_reduce_cyclotomic :: Ptr CUnityZp -> IO ()

_unity_zp_reduce_cyclotomic f

Sets \(f = f \bmod \Phi_{p^{exp}}\). \(\Phi_{p^{exp}}\) is the \(p^{exp}\)-th cyclotomic polynomial. \(g\) must be reduced by \(x^{p^{exp}}-1\) poly. \(f\) and \(g\) must be initialized with same \(p\), \(exp\) and \(n\).

unity_zp_reduce_cyclotomic :: Ptr CUnityZp -> Ptr CUnityZp -> IO ()

unity_zp_reduce_cyclotomic f g

Sets \(f = g \bmod \Phi_{p^{exp}}\). \(\Phi_{p^{exp}}\) is the \(p^{exp}\)-th cyclotomic polynomial.

Automorphism and inverse

unity_zp_aut :: Ptr CUnityZp -> Ptr CUnityZp -> CULong -> IO ()

unity_zp_aut f g x

Sets \(f = \sigma_x(g)\), the automorphism \(\sigma_x(\zeta)=\zeta^x\). \(f\) and \(g\) must be initialized with the same \(p\), \(exp\) and \(n\).

unity_zp_aut_inv :: Ptr CUnityZp -> Ptr CUnityZp -> CULong -> IO ()

unity_zp_aut_inv f g x

Sets \(f = \sigma_x^{-1}(g)\), so \(\sigma_x(f) = g\). \(g\) must be reduced by \(\Phi_{p^{exp}}\). \(f\) and \(g\) must be initialized with the same \(p\), \(exp\) and \(n\).

Jacobi sum

unity_zp_jacobi_sum_pq :: Ptr CUnityZp -> CULong -> CULong -> IO ()

unity_zp_jacobi_sum_pq f q p

Sets \(f\) to the Jacobi sum \(J(p, q) = j(\chi_{p, q}, \chi_{p, q})\).

unity_zp_jacobi_sum_2q_one :: Ptr CUnityZp -> CULong -> IO ()

unity_zp_jacobi_sum_2q_one f q

Sets \(f\) to the Jacobi sum \(J_2(q) = j(\chi_{2, q}^{2^{k - 3}}, \chi_{2, q}^{3 \cdot 2^{k - 3}}))^2\).

unity_zp_jacobi_sum_2q_two :: Ptr CUnityZp -> CULong -> IO ()

unity_zp_jacobi_sum_2q_two f q

Sets \(f\) to the Jacobi sum (J_3(1) = j(chi_{2, q}, chi_{2, q}, chi_{2, q}) = J(2, q) cdot j(chi_{2, q}^2, chi_{2, q})).

Extended rings

unity_zpq_init :: Ptr CUnityZpq -> CULong -> CULong -> Ptr CFmpz -> IO ()

unity_zpq_init f q p n

Initializes \(f\) as an element of \(\mathbb{Z}[\zeta_q, \zeta_p]/(n)\).

unity_zpq_clear :: Ptr CUnityZpq -> IO ()

unity_zpq_clear f

Clears the given element. It must be reinitialized in order to be used again.

unity_zpq_copy :: Ptr CUnityZpq -> Ptr CUnityZpq -> IO ()

unity_zpq_copy f g

Sets \(f\) to \(g\). \(f\) and \(g\) must be initialized with same \(p\), \(q\) and \(n\).

unity_zpq_swap :: Ptr CUnityZpq -> Ptr CUnityZpq -> IO ()

unity_zpq_swap f q

Swaps \(f\) and \(g\). \(f\) and \(g\) must be initialized with same \(p\), \(q\) and \(n\).

unity_zpq_equal :: Ptr CUnityZpq -> Ptr CUnityZpq -> IO CInt

unity_zpq_equal f g

Returns nonzero if \(f = g\).

unity_zpq_p_unity :: Ptr CUnityZpq -> IO CULong

unity_zpq_p_unity f

If \(f = \zeta_p^x\) returns \(x \in [0, p - 1]\); otherwise returns \(p\).

unity_zpq_is_p_unity :: Ptr CUnityZpq -> IO CInt

unity_zpq_is_p_unity f

Returns nonzero if \(f = \zeta_p^x\).

unity_zpq_is_p_unity_generator :: Ptr CUnityZpq -> IO CInt

unity_zpq_is_p_unity_generator f

Returns nonzero if \(f\) is a generator of the cyclic group \(\langle\zeta_p\rangle\).

unity_zpq_coeff_set_fmpz :: Ptr CUnityZpq -> CULong -> CULong -> Ptr CFmpz -> IO ()

unity_zpq_coeff_set_fmpz f i j x

Sets the coefficient of \(\zeta_q^i \zeta_p^j\) to \(x\). \(i\) must be less than \(q\) and \(j\) must be less than \(p\).

unity_zpq_coeff_set_ui :: Ptr CUnityZpq -> CULong -> CULong -> CULong -> IO ()

unity_zpq_coeff_set_ui f i j x

Sets the coefficient of \(\zeta_q^i \zeta_p^j\) to \(x\). \(i\) must be less than \(q\) and \(j\) must be less then \(p\).

unity_zpq_coeff_add :: Ptr CUnityZpq -> CULong -> CULong -> Ptr CFmpz -> IO ()

unity_zpq_coeff_add f i j x

Adds \(x\) to the coefficient of \(\zeta_p^i \zeta_q^j\). \(x\) must be less than \(n\).

unity_zpq_add :: Ptr CUnityZpq -> Ptr CUnityZpq -> Ptr CUnityZpq -> IO ()

unity_zpq_add f g h

Sets \(f\) to \(g + h\). \(f\), \(g\) and \(h\) must be initialized with same \(q\), \(p\) and \(n\).

unity_zpq_mul :: Ptr CUnityZpq -> Ptr CUnityZpq -> Ptr CUnityZpq -> IO ()

unity_zpq_mul f g h

Sets the \(f\) to \(g \cdot h\). \(f\), \(g\) and \(h\) must be initialized with same \(q\), \(p\) and \(n\).

_unity_zpq_mul_unity_p :: Ptr CUnityZpq -> IO ()

_unity_zpq_mul_unity_p f

Sets \(f = f \cdot \zeta_p\).

unity_zpq_mul_unity_p_pow :: Ptr CUnityZpq -> Ptr CUnityZpq -> CULong -> IO ()

unity_zpq_mul_unity_p_pow f g k

Sets \(f\) to \(g \cdot \zeta_p^k\).

unity_zpq_pow :: Ptr CUnityZpq -> Ptr CUnityZpq -> Ptr CFmpz -> IO ()

unity_zpq_pow f g p

Sets \(f\) to \(g^p\). \(f\) and \(g\) must be initialized with same \(p\), \(q\) and \(n\).

unity_zpq_pow_ui :: Ptr CUnityZpq -> Ptr CUnityZpq -> CULong -> IO ()

unity_zpq_pow_ui f g p

Sets \(f\) to \(g^p\). \(f\) and \(g\) must be initialized with same \(p\), \(q\) and \(n\).

unity_zpq_gauss_sum :: Ptr CUnityZpq -> CULong -> CULong -> IO ()

unity_zpq_gauss_sum f q p

Sets \(f = \tau(\chi_{p, q})\).

unity_zpq_gauss_sum_sigma_pow :: Ptr CUnityZpq -> CULong -> CULong -> IO ()

unity_zpq_gauss_sum_sigma_pow f q p

Sets \(f = \tau^{\sigma_n}(\chi_{p, q})\).