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 gg to h\sqrt{h} and 1/h1/\sqrt{h} modulo xnx^n. The constant term of hh must be a nonzero square modulo a prime n≠2n \ne 2 (it is usually 1), and its square root is chosen by nmod_sqrt; otherwise an exception is thrown. The underscore versions require hlen,n≥1\mathit{hlen}, n \ge 1, write nn coefficients and do not allow aliasing.

For short hh and nn 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 nn and Newton iteration for 1/h1/\sqrt{h} for large nn.

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