`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)source

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

@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-11-02}
}

Edit this page · PDF version · Built with fdoc from 0a4634bf95