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-10-20}
}