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 n config

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

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

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.

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.

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.

unity_zp_print f

Prints the contents of the \(f\).

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}\).

unity_zp_coeff_add_fmpz f ind x

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 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}\).

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\).

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 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\).

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\).

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

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\).

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})).

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\).

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

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})\).