fmpz_factor_pp1
#include <flint/fmpz_factor.h>Williams' p + 1 method [Wil1982]: looks for a factor of n with a stage 1 bound B1 and a stage 2 bound of at least \mathit{B2\_sqrt}^2, using the Lucas sequence with starting value c > 2. If a factor is found, sets factor to it and returns 1; otherwise returns 0. For even n it returns the factor 2.
The method finds a prime factor p when p - \left(\frac{c^2 - 4}{p}\right) is B1-smooth apart from at most one prime below the stage 2 bound. Since the Legendre symbol depends on c, which is unknown in advance, the method succeeds either for p + 1 or, as a p - 1 method, for p - 1; repeated calls with different random c give additional chances with roughly exponentially decaying probability of finding a missed factor. If neither p + 1 nor p - 1 is smooth for any prime factor p of n, the method never succeeds.
References#
- [Wil1982] H. C. Williams, "A p+1 method of factoring", Mathematics of Computation 39 (1982), 225–234
The FLINT team, “fmpz_factor_pp1 (fmpz_factor.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/fmpz_factor/fmpz_factor_pp1.html (generated 2026-10-20).
@misc{flint-doc-fmpz-factor-fmpz-factor-pp1,
author = {{The FLINT team}},
title = {{fmpz\_factor\_pp1 (fmpz\_factor.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/fmpz_factor/fmpz_factor_pp1.html},
note = {Generated 2026-10-20}
}