qsieve_square_root
Synopsis
#include <flint/qsieve.h>void qsieve_square_root(fmpz_t X, fmpz_t Y, qs_t qs_inf, uint64_t * nullrows, slong ncols, slong l, fmpz_t N)sourceFor the l-th null space vector, sets Y to the product of the Y values of the relations in it and X to the square root of the product of their factor base primes (from the halved exponent counts), both modulo N = kn. Then X^2 \equiv Y^2 \pmod{kn}, and \gcd(X - Y, n) is a factor of n, nontrivial with probability at least about 1/2 if n is not a prime power.
Cite this page
The FLINT team, “qsieve_square_root (qsieve.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/qsieve/qsieve_square_root.html (generated 2026-10-20).
@misc{flint-doc-qsieve-qsieve-square-root,
author = {{The FLINT team}},
title = {{qsieve\_square\_root (qsieve.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/qsieve/qsieve_square_root.html},
note = {Generated 2026-10-20}
}