n_factor_SQUFOF, n_ll_factor_SQUFOF
Synopsis
#include <flint/ulong_extras.h>Shanks' square form factorisation as described by Gower and Wagstaff [GowWag2008]. Returns a factor of n that fits in one limb, or 0 if none was found within iters iterations. The ll version takes a two-limb n = n_{hi} B + n_{lo}.
SQUFOF is first tried on n itself and then on kn for the small primes k in flint_primes_small. The product may need two limbs, which the implementation supports; SQUFOF itself only works with numbers about the size of \sqrt n.
References#
- [GowWag2008] Jason Gower and Sam Wagstaff : "Square form factoring" Math. Comp. 77, 2008, pp 551-588, https://doi.org/10.1090/S0025-5718-07-02010-8
Cite this page
The FLINT team, “n_factor_SQUFOF, n_ll_factor_SQUFOF (ulong_extras.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/ulong_extras/n_factor_SQUFOF.html (generated 2026-10-20).
@misc{flint-doc-ulong-extras-n-factor-SQUFOF,
author = {{The FLINT team}},
title = {{n\_factor\_SQUFOF, n\_ll\_factor\_SQUFOF (ulong\_extras.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/ulong_extras/n_factor_SQUFOF.html},
note = {Generated 2026-10-20}
}