FLINT3.7.0-dev
/

fmpz_factor_pp1

Synopsis#include <flint/fmpz_factor.h>
int fmpz_factor_pp1(fmpz_t factor, const fmpz_t n, ulong B1, ulong B2_sqrt, ulong c)source

Williams' p+1p + 1 method [Wil1982]: looks for a factor of nn with a stage 1 bound B1 and a stage 2 bound of at least B2_sqrt2\mathit{B2\_sqrt}^2, using the Lucas sequence with starting value c>2c > 2. If a factor is found, sets factor to it and returns 1; otherwise returns 0. For even nn it returns the factor 2.

The method finds a prime factor pp when p−(c2−4p)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 cc, which is unknown in advance, the method succeeds either for p+1p + 1 or, as a p−1p - 1 method, for p−1p - 1; repeated calls with different random cc give additional chances with roughly exponentially decaying probability of finding a missed factor. If neither p+1p + 1 nor p−1p - 1 is smooth for any prime factor pp of nn, the method never succeeds.

References#

  • [Wil1982] H. C. Williams, "A p+1 method of factoring", Mathematics of Computation 39 (1982), 225–234
Cite this page

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-11-02).