FLINT3.7.0-dev
/

_nmod_poly_sqrt_series, nmod_poly_sqrt_series, _nmod_poly_invsqrt_series, nmod_poly_invsqrt_series

Synopsis#include <flint/nmod_poly.h>
void _nmod_poly_sqrt_series(nn_ptr g, nn_srcptr h, slong hlen, slong n, nmod_t mod)source
void nmod_poly_sqrt_series(nmod_poly_t g, const nmod_poly_t h, slong n)source
void _nmod_poly_invsqrt_series(nn_ptr g, nn_srcptr h, slong hlen, slong n, nmod_t mod)source
void nmod_poly_invsqrt_series(nmod_poly_t g, const nmod_poly_t h, slong n)source

Set g to \sqrt{h} and 1/\sqrt{h} modulo x^n. The constant term of h must be a nonzero square modulo a prime n \ne 2 (it is usually 1), and its square root is chosen by nmod_sqrt; otherwise an exception is thrown. The underscore versions require \mathit{hlen}, n \ge 1, write n coefficients and do not allow aliasing.

For short h and n larger than the length the coefficients follow from a linear recurrence (J. C. P. Miller's method for powers of power series, [Knu1997, §4.7]), which requires the series length to be less than the modulus. Otherwise the basecase algorithm is used for small n and Newton iteration for 1/\sqrt{h} for large n.

References#

  • [Knu1997] Knuth, D. E. The Art of Computer Programming, volume 2: Seminumerical algorithms, 1997
Cite this page

The FLINT team, “_nmod_poly_sqrt_series, nmod_poly_sqrt_series, _nmod_poly_invsqrt_series, nmod_poly_invsqrt_series (nmod_poly.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/nmod_poly/_nmod_poly_sqrt_series.html (generated 2026-10-20).