FLINT3.7.0-dev
/

ecpp_cornacchia

Synopsis#include <flint/ecpp.h>
int ecpp_cornacchia(fmpz_t t, fmpz_t v, const fmpz_t n, slong D, const fmpz_t sqrtD)source

Given D<0D < 0, an odd nn with gcd⁡(n,D)=1\gcd(n, D) = 1 and a square root of DD modulo nn, finds t,v≥0t, v \ge 0 with t2+∣D∣v2=4nt^2 + |D| v^2 = 4n and returns 1, or returns 0 if there is no solution (Cornacchia's algorithm in the form of Cohen [Coh1996, Algorithm 1.5.3]).

References#

  • [Coh1996] Cohen, Henri : A course in computational algebraic number theory, Springer, 1996
Cite this page

The FLINT team, “ecpp_cornacchia (ecpp.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/ecpp/ecpp_cornacchia.html (generated 2026-11-02).