flint_mpn_sqrtmod, flint_mpn_sqrtmod_preinv
#include <flint/mpn_extras.h>int flint_mpn_sqrtmod_preinv(nn_ptr res, nn_srcptr a, nn_srcptr d, mp_size_t n, nn_srcptr dinv, flint_bitcnt_t norm)sourceSets (\mathit{res}, n) to a square root of a modulo the odd prime d and returns 1. Returns 0, setting res to zero, if the Jacobi symbol rules a root out (which is conclusive whether or not d is prime), and -1, again setting res to zero, if the algorithm itself failed, which happens only for d not prime (or, with negligible probability, for a prime whose least quadratic nonresidue exceeds 2^{20}). The preinv version takes the inverse dinv of d 2^{\mathrm{norm}} from flint_mpn_preinvn and \mathrm{norm} = \mathrm{clz}(d_{n-1}), as an mpn_mod or fmpz_mod context holds them; dinv may be NULL.
For d - 1 = q 2^s with q odd, the root is a single exponentiation when s \le 2 (a^{(d+1)/4}, or Atkin's formula); Tonelli–Shanks is used for 3 \le s < 32, and Müller's variant of the Cipolla–Lehmer algorithm, whose cost does not depend on s, for s \ge 32. See Square roots modulo a prime. The arithmetic is flint_mpn_mulmod_preinvn and flint_mpn_powmod_preinvn throughout.
The FLINT team, “flint_mpn_sqrtmod, flint_mpn_sqrtmod_preinv (mpn_extras.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/mpn_extras/flint_mpn_sqrtmod.html (generated 2026-10-20).
@misc{flint-doc-mpn-extras-flint-mpn-sqrtmod,
author = {{The FLINT team}},
title = {{flint\_mpn\_sqrtmod, flint\_mpn\_sqrtmod\_preinv (mpn\_extras.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/mpn_extras/flint_mpn_sqrtmod.html},
note = {Generated 2026-10-20}
}