FLINT3.7.0-dev
/

_aprcl_is_prime_jacobi

Synopsis#include <flint/aprcl.h>
primality_test_status _aprcl_is_prime_jacobi(const fmpz_t n, const aprcl_config config)source

The Jacobi sum test for nn with the given configuration. Returns PRIME, COMPOSITE or UNKNOWN, the latter also when the configuration does not satisfy s2>ns^2 > n.

The steps are those of Cohen's Algorithm 9.1.28: a check that nn is coprime to RsRs; for every prime q∣sq \mid s and every prime power pk ∥ q−1p^k \,\|\, q - 1, the test that J0uJvJ_0^u J_v is a root of unity in Z[ζpk]/(n)\mathbb{Z}[\zeta_{p^k}]/(n) (the pairs (p,q)(p, q) are independent tasks, distributed over the available threads in decreasing order of cost); the conditions (Lp)(\mathcal L_p), completed by additional tests with an extra prime qq where needed; and the final division (aprcl_is_prime_final_division). Moduli of 2 to 16 limbs use the unity_zp_mpn arithmetic, larger ones the unity_zp arithmetic.

Cite this page

The FLINT team, “_aprcl_is_prime_jacobi (aprcl.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/aprcl/_aprcl_is_prime_jacobi.html (generated 2026-11-02).