aprcl.h – APRCL primality testing¶
This module implements the rigorous APRCL primality test, suitable for integers up to a few thousand digits.
The APRCL test uses the Jacobi sums that belong to
\(\mathbb{Z}[\zeta]/(n)\), so we have unity_zp
struct and some
useful operations. unity_zp
is just a wrapper over
fmpz_mod_poly
with additional fields.
Also provides Gauss sum test, which is not very useful in practice,
but can be useful for people who want to see an implementation of
these. Gauss sums belong \(\mathbb{Z}[\zeta_q, \zeta_p]/(n)\) and
implemented in unity_zpq
struct.
Authors:
Vladimir Glazachev (Google Summer of Code, 2015)
Primality test functions¶

int aprcl_is_prime(const fmpz_t n)¶
Tests \(n\) for primality using the APRCL test. This is the same as
aprcl_is_prime_jacobi()
.

int aprcl_is_prime_jacobi(const fmpz_t 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.

int aprcl_is_prime_gauss(const fmpz_t 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.

primality_test_status _aprcl_is_prime_jacobi(const fmpz_t n, const aprcl_config config)¶
Jacobi sum test for \(n\). Possible return values:
PRIME
,COMPOSITE
andUNKNOWN
(if we cannot prove primality).

primality_test_status _aprcl_is_prime_gauss(const fmpz_t n, const aprcl_config config)¶
Tests \(n\) for primality with fixed
config
. Possible return values:PRIME
,COMPOSITE
andPROBABPRIME
(if we cannot prove primality).

int aprcl_is_prime_gauss_min_R(const fmpz_t n, ulong R)¶
Same as
aprcl_is_prime_gauss()
with fixed minimum value of \(R\).
Configuration functions¶

type _aprcl_config¶

type aprcl_config¶
Holds precomputed parameters.

void aprcl_config_gauss_init(aprcl_config conf, const fmpz_t n)¶
Computes the \(s\) and \(R\) values used in the cyclotomic primality test, \(s^2 > n\) and \(s=\prod\limits_{\substack{q1\mid R \\ q \text{ prime}}}q\). Also stores factors of \(R\) and \(s\).

void aprcl_config_gauss_init_min_R(aprcl_config conf, const fmpz_t n, ulong R)¶
Computes the \(s\) with fixed minimum \(R\) such that \(a^R \equiv 1 \mod{s}\) for all integers \(a\) coprime to \(s\).

void aprcl_config_gauss_clear(aprcl_config conf)¶
Clears the given
aprcl_config
element. It must be reinitialised in order to be used again.

ulong aprcl_R_value(const fmpz_t 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.

void aprcl_config_jacobi_init(aprcl_config conf, const fmpz_t 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\).

void aprcl_config_jacobi_clear(aprcl_config conf)¶
Clears the given
aprcl_config
element. It must be reinitialised in order to be used again.
Cyclotomic arithmetic¶
This code implements arithmetic in cyclotomic rings.
Types¶

type _unity_zp¶

type unity_zp¶
Represents an element of \(\mathbb{Z}[\zeta_{p^{exp}}]/(n)\) as an
fmpz_mod_poly_t
reduced modulo a cyclotomic polynomial.

type _unity_zpq¶

type unity_zpq¶
Represents an element of \(\mathbb{Z}[\zeta_q, \zeta_p]/(n)\) as an array of
fmpz_mod_poly_t
.
Memory management¶

void unity_zp_init(unity_zp f, ulong p, ulong exp, const fmpz_t n)¶
Initializes \(f\) as an element of \(\mathbb{Z}[\zeta_{p^{exp}}]/(n)\).

void unity_zp_clear(unity_zp f)¶
Clears the given element. It must be reinitialised in order to be used again.

void unity_zp_copy(unity_zp f, const unity_zp g)¶
Sets \(f\) to \(g\). \(f\) and \(g\) must be initialized with same \(p\) and \(n\).
Comparison¶
Coefficient management¶

void unity_zp_coeff_set_fmpz(unity_zp f, ulong ind, const fmpz_t x)¶

void unity_zp_coeff_set_ui(unity_zp f, ulong ind, ulong x)¶
Sets the coefficient of \(\zeta^{ind}\) to \(x\). \(ind\) must be less than \(p^{exp}\).

void unity_zp_coeff_add_fmpz(unity_zp f, ulong ind, const fmpz_t x)¶

void unity_zp_coeff_add_ui(unity_zp f, ulong ind, ulong x)¶
Adds \(x\) to the coefficient of \(\zeta^{ind}\). \(x\) must be less than \(n\). \(ind\) must be less than \(p^{exp}\).
Scalar multiplication¶
Addition and multiplication¶

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

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

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

void unity_zp_mul_inplace(unity_zp f, const unity_zp g, const unity_zp h, fmpz_t *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\).

void unity_zp_sqr_inplace(unity_zp f, const unity_zp g, fmpz_t *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¶

void unity_zp_pow_fmpz(unity_zp f, const unity_zp g, const fmpz_t pow)¶
Sets \(f\) to \(g^{pow}\). \(f\) and \(g\) must be initialized with same \(p\), \(exp\) and \(n\).

void unity_zp_pow_ui(unity_zp f, const unity_zp g, ulong pow)¶
Sets \(f\) to \(g^{pow}\). \(f\) and \(g\) must be initialized with same \(p\), \(exp\) and \(n\).

ulong _unity_zp_pow_select_k(const fmpz_t n)¶
Returns the smallest integer \(k\) satisfying \(\log (n) < (k(k + 1)2^{2k}) / (2^{k + 1}  k  2) + 1\)

void unity_zp_pow_2k_fmpz(unity_zp f, const unity_zp g, const fmpz_t 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\).
Cyclotomic reduction¶

void _unity_zp_reduce_cyclotomic_divmod(unity_zp f)¶

void _unity_zp_reduce_cyclotomic(unity_zp 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\).
Automorphism and inverse¶
Jacobi sum¶
Here \(\chi_{p, q}\) is the character defined by \(\chi_{p, q}(g^x) = \zeta_{p^k}^x\), where \(g\) is a primitive root modulo \(q\).

void unity_zp_jacobi_sum_pq(unity_zp f, ulong q, ulong p)¶
Sets \(f\) to the Jacobi sum \(J(p, q) = j(\chi_{p, q}, \chi_{p, q})\).
Extended rings¶

void unity_zpq_init(unity_zpq f, ulong q, ulong p, const fmpz_t n)¶
Initializes \(f\) as an element of \(\mathbb{Z}[\zeta_q, \zeta_p]/(n)\).

void unity_zpq_clear(unity_zpq f)¶
Clears the given element. It must be reinitialized in order to be used again.

void unity_zpq_copy(unity_zpq f, const unity_zpq g)¶
Sets \(f\) to \(g\). \(f\) and \(g\) must be initialized with same \(p\), \(q\) and \(n\).

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

void unity_zpq_coeff_set_fmpz(unity_zpq f, slong i, slong j, const fmpz_t 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\).

void unity_zpq_coeff_set_ui(unity_zpq f, slong i, slong j, ulong 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\).

void unity_zpq_coeff_add(unity_zpq f, slong i, slong j, const fmpz_t x)¶
Adds \(x\) to the coefficient of \(\zeta_p^i \zeta_q^j\). \(x\) must be less than \(n\).

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

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

void unity_zpq_mul_unity_p_pow(unity_zpq f, const unity_zpq g, slong k)¶
Sets \(f\) to \(g \cdot \zeta_p^k\).

void unity_zpq_pow(unity_zpq f, const unity_zpq g, const fmpz_t p)¶
Sets \(f\) to \(g^p\). \(f\) and \(g\) must be initialized with same \(p\), \(q\) and \(n\).