Flint2-0.1.0.5: Haskell bindings for the flint library for number theory

Data.Number.Flint.APRCL

Synopsis

# APRCL primality testing

Constructors

 Gauss !(ForeignPtr CAPRCLConfig) Jacobi !(ForeignPtr CAPRCLConfig)

Constructors

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

#### Instances

Instances details
 Source # Instance detailsDefined in Data.Number.Flint.APRCL.FFI MethodspeekByteOff :: Ptr b -> Int -> IO CAPRCLConfig #pokeByteOff :: Ptr b -> Int -> CAPRCLConfig -> IO () #

# Primality test functions

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 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 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 Source #

_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 Source #

_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 n R

Same as aprcl_is_prime_gauss with fixed minimum value of $$R$$.

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 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 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 conf

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

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 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 conf

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

# Cyclotomic arithmetic

data UnityZp Source #

Constructors

 UnityZp !(ForeignPtr CUnityZp)

data CUnityZp Source #

Constructors

 CUnityZp (Ptr CFmpzModPoly) CULong CULong (Ptr CFmpzModCtx)

#### Instances

Instances details
 Source # Instance detailsDefined in Data.Number.Flint.APRCL.FFI MethodspokeElemOff :: Ptr CUnityZp -> Int -> CUnityZp -> IO () #peekByteOff :: Ptr b -> Int -> IO CUnityZp #pokeByteOff :: Ptr b -> Int -> CUnityZp -> IO () #poke :: Ptr CUnityZp -> CUnityZp -> IO () #

data UnityZpq Source #

Constructors

 UnityZpq !(ForeignPtr CUnityZpq)

#### Instances

Instances details
 Source # Instance detailsDefined in Data.Number.Flint.APRCL.FFI MethodspokeElemOff :: Ptr CUnityZpq -> Int -> CUnityZpq -> IO () #peekByteOff :: Ptr b -> Int -> IO CUnityZpq #pokeByteOff :: Ptr b -> Int -> CUnityZpq -> IO () #poke :: Ptr CUnityZpq -> CUnityZpq -> IO () #

# Memory management

unity_zp_init f p exp n

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

unity_zp_clear f

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

unity_zp_copy f g

Sets $$f$$ to $$g$$. $$f$$ and $$g$$ must be initialized with same $$p$$ and $$n$$.

unity_zp_swap f q

Swaps $$f$$ and $$g$$. $$f$$ and $$g$$ must be initialized with same $$p$$ and $$n$$.

unity_zp_set_zero f

Sets $$f$$ to zero.

# Comparison

unity_zp_is_unity f

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

unity_zp_equal f g

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

# Output

unity_zp_print f

Prints the contents of the $$f$$.

# Coefficient management

unity_zp_coeff_set_fmpz f ind x

unity_zp_coeff_set_ui f ind x

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

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 f ind

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

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 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 f g s

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

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

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 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 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 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 f g pow

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

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 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 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 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 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 f

_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 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 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 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 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 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 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 f q p n

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

unity_zpq_clear f

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

unity_zpq_copy f g

Sets $$f$$ to $$g$$. $$f$$ and $$g$$ must be initialized with same $$p$$, $$q$$ and $$n$$.

unity_zpq_swap f q

Swaps $$f$$ and $$g$$. $$f$$ and $$g$$ must be initialized with same $$p$$, $$q$$ and $$n$$.

unity_zpq_equal f g

Returns nonzero if $$f = g$$.

unity_zpq_p_unity f

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

unity_zpq_is_p_unity f

Returns nonzero if $$f = \zeta_p^x$$.

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

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

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

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 f

Sets $$f = f \cdot \zeta_p$$.

unity_zpq_mul_unity_p_pow f g k

Sets $$f$$ to $$g \cdot \zeta_p^k$$.

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 f g p

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

unity_zpq_gauss_sum f q p

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

unity_zpq_gauss_sum_sigma_pow f q p

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