FLINT3.7.0-dev
/

fq_sqrt

Synopsis#include <flint/fq.h>
int fq_sqrt(fq_t rop, const fq_t op, const fq_ctx_t ctx)source

If op is a square, sets rop to a square root of it and returns 1; otherwise returns 0, and rop is unspecified.

For p = 2 the square root is the inverse of the Frobenius map, computed by fq_pth_root. For odd p the function uses the Tonelli–Shanks algorithm [Ton1891] [Sha1973] in the cyclic group \mathbb{F}_q^\times of order q - 1 = 2^s t, t odd: it needs a quadratic non-residue z, which is the generator if the context was created from a Conway polynomial (a primitive element is never a square) and is found by random sampling otherwise, and then O(s^2) multiplications after three exponentiations.

References#

  • [Ton1891] A. Tonelli, "Bemerkung über die Auflösung quadratischer Congruenzen", Nachrichten von der Königlichen Gesellschaft der Wissenschaften und der Georg-Augusts-Universität zu Göttingen (1891), 344–346
  • [Sha1973] D. Shanks, "Five number-theoretic algorithms", Proceedings of the Second Manitoba Conference on Numerical Mathematics, Congressus Numerantium 7 (1973), 51–70
Cite this page

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