mpn_mod_is_square, mpn_mod_sqrt

$0$ and $1$ are squares for every modulus, and mpn_mod_sqrt returns them unchanged. Otherwise both functions use the Jacobi symbol $\left(\frac{x}{n}\right)$ for odd $n$ (flint_mpn_is_square_mod). A symbol of $-1$ proves that $x$ is not a square, whether or not $n$ is prime: mpn_mod_is_square returns T_FALSE and mpn_mod_sqrt sets res to zero and returns GR_DOMAIN. A symbol of $+1$ gives T_TRUE if the context is flagged as prime and T_UNKNOWN otherwise; for even $n$, mpn_mod_is_square returns T_UNKNOWN.

mpn_mod_sqrt computes roots only for odd moduli flagged as prime (gr_ctx_set_is_field), with flint_mpn_sqrtmod_preinv and the precomputed inverse of the context (an exponentiation, Atkin's formula, Tonelli–Shanks or Müller's variant of the Cipolla–Lehmer algorithm depending on the 2-adic valuation of $n - 1$; see Square roots modulo a prime). For even moduli, and for odd moduli not flagged as prime when the Jacobi symbol is $+1$, it returns GR_UNABLE. If the algorithm fails, which can only happen if the flag was wrong, it also returns GR_UNABLE.

@misc{flint-doc-mpn-mod-mpn-mod-is-square,
  author       = {{The FLINT team}},
  title        = {{mpn\_mod\_is\_square, mpn\_mod\_sqrt (mpn\_mod.h)}},
  howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
  year         = {2026},
  url          = {https://flintlib.org/doc/mpn_mod/mpn_mod_is_square.html},
  note         = {Generated 2026-11-02}
}