FLINT3.7.0-dev
/

flint_mpn_sqrtmod, flint_mpn_sqrtmod_preinv

Synopsis#include <flint/mpn_extras.h>
int flint_mpn_sqrtmod(nn_ptr res, nn_srcptr a, nn_srcptr d, mp_size_t n)source
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)source

Sets (res,n)(\mathit{res}, n) to a square root of aa modulo the odd prime dd and returns 1. Returns 0, setting res to zero, if the Jacobi symbol rules a root out (which is conclusive whether or not dd is prime), and −1-1, again setting res to zero, if the algorithm itself failed, which happens only for dd not prime (or, with negligible probability, for a prime whose least quadratic nonresidue exceeds 2202^{20}). The preinv version takes the inverse dinv of d2normd 2^{\mathrm{norm}} from flint_mpn_preinvn and norm=clz(dn−1)\mathrm{norm} = \mathrm{clz}(d_{n-1}), as an mpn_mod or fmpz_mod context holds them; dinv may be NULL.

For d−1=q2sd - 1 = q 2^s with qq odd, the root is a single exponentiation when s≤2s \le 2 (a(d+1)/4a^{(d+1)/4}, or Atkin's formula); Tonelli–Shanks is used for 3≤s<323 \le s < 32, and Müller's variant of the Cipolla–Lehmer algorithm, whose cost does not depend on ss, for s≥32s \ge 32. See Square roots modulo a prime. The arithmetic is flint_mpn_mulmod_preinvn and flint_mpn_powmod_preinvn throughout.

Cite this page

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