aprcl.h

Return 1 if n is prime and 0 if it is not (in particular for n < 2), using the Jacobi sum test with the parameters chosen by aprcl_config_jacobi_init. aprcl_is_prime is the same function. If the test cannot decide (which would require that no suitable auxiliary prime exists for one of the additional tests, and has not been observed), an exception is thrown; _aprcl_is_prime_jacobi returns UNKNOWN instead. Above about 20000 bits (6000 digits) the configuration extends the tabulated R so that s^2 > n still holds, but ecpp_is_prime is then usually much faster.

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

Return 1 if n is prime and 0 otherwise, using the Gauss sum test in the form described by Schoof [Sch2008], with the minimum value R respectively 180. If the conditions (\mathcal L_p) cannot be verified, aprcl_is_prime_gauss retries with R multiplied by 2, 3 and 5 before throwing an exception. This version is much slower than the Jacobi sum test.

The Gauss sum test for n with the given configuration. Returns PRIME, COMPOSITE or PROBABPRIME (if primality could not be proved with this R, or the configuration does not satisfy s^2 > n).

The final step of the test: given that every divisor of n is congruent to n^i \bmod s for some 0 \le i < r, and \gcd(n, s) = 1, returns 0 if n is divisible by one of the residues a = n^i \bmod s with 1 < a \le \sqrt n, 1 \le i < r, and 1 otherwise. If s^2 > n, a return value of 1 proves that n is prime. The walk through the residues is parallelised when threads are available.

Returns the value of R from a precomputed table, chosen by the bit size of n so that the corresponding s satisfies s^2 > n and the test is fast: from R = 6 for n < 2^{17} to R = 1396755360 up to 12713 bits, and R = 6983776800 (for which s has about 10000 bits, enough up to 20004 bits) beyond. For larger n this s is too small, and aprcl_config_jacobi_init extends R. On 32-bit machines inputs beyond 12713 bits raise an exception.

Initialise conf for the Jacobi sum test of n, with R from aprcl_R_value respectively the given R, and free it. If the value of aprcl_R_value does not give s^2 > n, aprcl_config_jacobi_init multiplies R by the next primes after its largest prime factor until it does (throwing an exception if R would overflow a word). The full s for R is reduced by dropping the prime powers q^e whose tests are the most expensive per bit contributed to s (estimated from the sizes of \varphi(p^k) for p^k \| q - 1, and very large q first) as long as s^2 > n remains.

Initialise conf for the Gauss sum test of n, choosing the least suitable R (respectively the least suitable R that is a multiple of the given one) with s^2 > n, and free it.

Return 1 if \gcd(xy, n) = 1 and 0 otherwise.

Returns the exponent of the prime p in q > 0.

Returns the index of the prime p in the factorisation of R stored in conf, or -1 if p \nmid R.

The check for odd p (with j = J(p, q)), for p^k = 2 (which reduces to (-q)^{(n-1)/2} \equiv \pm 1 \pmod n, returning 0 for +1, 1 for -1 and -1 otherwise), for p^k = 4 (with j = J(2, q); h gives \zeta_4^h \in \{1, i, -1, -i\}), and for p = 2, k \ge 3 (with j = J(2, q), j_{2,1} = J_3(q) and j_{2,2} = J_2(q)).

The same checks with unity_zp_mpn arithmetic. They return 0 without computing anything if the modulus is not supported by mpn_mod (fewer than 2 or more than 16 limbs), in which case the caller falls back to the unity_zp versions; otherwise they return 1 and store the result in *h.

The additional test of step 5 for a prime p \mid R for which (\mathcal L_p) was not established: looks for a prime q \equiv 1 \pmod{2p} (with 4 \| q - 1 if p = 2) such that n^{(q-1)/p} \not\equiv 1 \pmod q and checks that the corresponding h is a primitive root of unity (and for p = 2 that q^{(n-1)/2} \equiv -1 \pmod n). Returns 2 if n is proved composite, 1 if the condition holds, and 0 if no suitable q was found.

Checks of the Gauss sum test, for the Gauss sum \tau(\chi) of a character \chi of conductor q: whether (\chi(-1) q)^{(n-1)/2} \equiv -1 \pmod n and whether q^{(n-1)/2} \equiv -1 \pmod n (for the quadratic character, returning 1 or 0), and for a character of order r, returns i such that \tau(\chi^n) = \zeta_r^i \tau(\chi)^n, or -1 if there is none.

Initialise f as the zero element of \mathbb{Z}[\zeta_{p^{exp}}]/(n), and free it.

Copy, swap and set to zero.

unity_zp_is_unity returns h if f = \zeta^h and -1 otherwise; unity_zp_equal returns whether f = g after reduction by \Phi_{p^{exp}}.

Set, add to, increment or decrement the coefficient of \zeta^{ind}, for \mathit{ind} < p^{exp}. The added x must be less than n.

Set f to sg, respectively g + h.

Set f to gh, respectively g^2, reduced by \Phi_{p^{exp}} and n. The inplace versions use the preallocated array t of SQUARING_SPACE values as temporary space when it is large enough.

Sets f to gh (or g^2 if h is g) reduced by \Phi_{p^{exp}} and modulo n: the product over the integers is computed by _fmpz_poly_mul or _fmpz_poly_sqr into t (which must hold at least g->poly->length + h->poly->length - 1 initialised values), the cyclotomic reduction is done there with additions and subtractions (first by x^{p^{exp}} = 1, then by \Phi_{p^{exp}}(x) = \Phi_p(x^{p^{exp-1}})), and each of the \varphi(p^{exp}) remaining coefficients is reduced modulo n once. The operands need not be reduced by \Phi_{p^{exp}}.

If a hand-optimised straight-line program exists for p^{exp} (currently 3, 4, 5, 7, 8, 9 and 16), the operands have full length \varphi(p^{exp}) and the modulus is small enough (a few thousand bits) that the smaller number of multiplications pays off, compute the reduced product (or square) using t (at least SQUARING_SPACE values) as temporary space and return 1; otherwise return 0.

Set f to g^{\mathit{pow}}, by binary exponentiation, by the 2^k-ary method with k from _unity_zp_pow_select_k, and by sliding window exponentiation.

Returns the least k with \log n < k(k + 1) 2^{2k} / (2^{k + 1} - k - 2) + 1, the window size for an exponent of the size of n.

Set f = g \bmod \Phi_{p^{exp}}, respectively reduce f in place (by additions, or by polynomial division); the in-place versions require f to be reduced modulo x^{p^{exp}} - 1.

Set f = \sigma_x(g) for the automorphism \sigma_x(\zeta) = \zeta^x, respectively f = \sigma_x^{-1}(g); for the latter g must be reduced by \Phi_{p^{exp}}.

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

For p = 2, set f to J_2(q) = j(\chi_{2,q}^{2^{k-3}}, \chi_{2,q}^{3 \cdot 2^{k-3}})^2, respectively J_3(q) = j(\chi_{2,q}, \chi_{2,q}, \chi_{2,q}) = J(2, q)\, j(\chi_{2,q}^2, \chi_{2,q}).

Returns a table (allocated with _nmod_vec_init) of the discrete logarithms f(x) with g^{f(x)} = 1 - g^x \pmod q for a primitive root g modulo the prime q, from which the Jacobi sums are computed.

Sets f to \sum_{x=1}^{q-2} \zeta_{p^k}^{ax + b f(x)}, given the table of aprcl_f_table.

Initialise f as the zero element of \mathbb{Z}[\zeta_{p^{exp}}]/(n), where ctx is an mpn_mod context with modulus n (borrowed: it must outlive f), and free it.

Set to zero, swap, copy, set the coefficient of \zeta^{ind} to x (for any \mathit{ind} < p^{exp}, exponents of at least \varphi(p^{exp}) being folded by the cyclotomic relation), and convert from a unity_zp with the same p, k and n.

Product, square, scalar multiple and powers (the last by sliding window exponentiation). The output may alias the inputs.

f = \sigma_x^{-1}(g) (f and g must not be aliased), and the exponent h with f = \zeta^h, or -1.

Initialise as zero, free, copy, swap and compare.

Set or add to the coefficient of \zeta_q^i \zeta_p^j, for i < q and j < p; the added x must be less than n.

Sum, product, multiplication of f by \zeta_p in place, f = g \zeta_p^k (the last argument being k), and powers.

Set f to the Gauss sum \tau(\chi_{p,q}) = \sum_x \chi_{p,q}(x) \zeta_q^x, to \tau(\chi_{p,q}^{\mathit{pow}}), and to \sigma_n(\tau(\chi_{p,q})).