fmpz_divisor_in_residue_class_lenstra
Synopsis
#include <flint/fmpz.h>int fmpz_divisor_in_residue_class_lenstra(fmpz_t fac, const fmpz_t n, const fmpz_t r, const fmpz_t s)sourceLenstra's algorithm: for 0 < r < s < n with \gcd(r, s) = 1, finds a divisor of n congruent to r modulo s if there is one, sets fac to it and returns 1; otherwise returns 0. Efficient when s^3 > n, as in the final step of the n \pm 1 primality tests.
Cite this page
The FLINT team, “fmpz_divisor_in_residue_class_lenstra (fmpz.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/fmpz/fmpz_divisor_in_residue_class_lenstra.html (generated 2026-10-20).
@misc{flint-doc-fmpz-fmpz-divisor-in-residue-class-lenstra,
author = {{The FLINT team}},
title = {{fmpz\_divisor\_in\_residue\_class\_lenstra (fmpz.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/fmpz/fmpz_divisor_in_residue_class_lenstra.html},
note = {Generated 2026-10-20}
}