`aprcl_is_prime_final_division`

Synopsis#include <flint/aprcl.h>

int aprcl_is_prime_final_division(const fmpz_t n, const fmpz_t s, ulong r)source

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.

Cite this page

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

@misc{flint-doc-aprcl-aprcl-is-prime-final-division,
  author       = {{The FLINT team}},
  title        = {{aprcl\_is\_prime\_final\_division (aprcl.h)}},
  howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
  year         = {2026},
  url          = {https://flintlib.org/doc/aprcl/aprcl_is_prime_final_division.html},
  note         = {Generated 2026-11-02}
}

Edit this page · PDF version · Built with fdoc from 0a4634bf95