FLINT3.7.0-dev
/

flint_mpn_sqrt

Synopsis#include <flint/mpn_extras.h>
int flint_mpn_sqrt(mp_ptr s, mp_srcptr a, mp_size_t an)source

Checked exact square root, the analogue of flint_mpn_div: if aa is a perfect square, sets (s,⌈an/2⌉)(s, \lceil \mathit{an}/2 \rceil) to its square root and returns 1; otherwise returns 0, the contents of ss being undefined. Requires aan−1≠0a_{an-1} \ne 0.

Nonsquares are usually rejected before any root is computed by quadratic residue tests modulo 256 and modulo the factors 9, 5, 7, 13, 17, 97, 241 and 257 of 248−12^{48} - 1, all obtained from one reduction modulo 248−12^{48} - 1 (flint_mpn_mod_2exp48m1); about one random nonsquare in 900 survives. On 32-bit builds the residues come from two mpn_mod_1 calls instead.

Cite this page

The FLINT team, “flint_mpn_sqrt (mpn_extras.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/mpn_extras/flint_mpn_sqrt.html (generated 2026-11-02).