ecpp.h

Attempts to prove that n is prime. Returns 1 and fills cert with a certificate if n is prime, 0 if n is composite (or n \le 1), and -1 if no proof could be found. For n < 2^{64} the certificate is empty and primality is decided by fmpz_is_prime. The input is first subjected to a BPSW test, so composites are detected quickly.

Returns 1 if cert is a valid certificate proving that n is prime, and 0 otherwise. An empty certificate is valid exactly for primes n < 2^{64}.

Checks one step: returns 1 if it proves that its n is prime provided that its q is prime, and 0 otherwise.

Runs ecpp_prove and discards the certificate; same return values.

With verbose nonzero, ecpp_prove prints each step as it is found (the sizes, the discriminant, the class number and the degree of the polynomial whose root is needed). The setting is global.

Initialise an empty certificate, and free it.

Append a new step (with initialised fields) and return a pointer to it, respectively remove the last step.

Print the certificate in the given format to stdout or to file, or return it as a string to be freed with flint_free.

Reads a certificate in either format (recognised by its first character). Returns 1 on success, and 0, leaving an empty certificate, if the string is malformed. In the PARI/GP format, b is recovered from the point and the discriminant is not available (it is set to 0); the certificate verifies all the same.

Initialise and free a point, set it to the affine point (x, y) (with Z = 1), and test whether it is the point at infinity.

Sets R = kP on the curve with coefficient a modulo the modulus n of ctx, for an affine point P and k \ge 0. Every quantity whose invertibility the formulas assume is multiplied into acc; the result is meaningful only if \gcd(\mathit{acc}, n) = 1 at the end, and otherwise n is composite. Returns 0 if acc became zero and 1 otherwise.

Initialises gctx as the ring of integers modulo the modulus of ctx: mpn_mod for moduli of 2 to MPN_MOD_MAX_LIMBS limbs, and fmpz_mod otherwise.

The scalar multiplication over a generic ring (a point being three consecutive elements X, Y, Z), on which ecpp_point_mul is built after converting to the ring given by ecpp_gr_ctx_init.

Sets *table (allocated with flint_malloc) to the fundamental discriminants -D_{\max} \le D < 0 of class number at most hmax, odd part of the class number at most omax and cost at most costmax, whose odd prime factors are among the nprimes odd primes in primes, and returns their number. They are sorted by number of units, odd part of the class number, cost and |D|. The class numbers are computed with a cache-blocked sieve over reduced forms.

The estimated cost of realising a step with the discriminant d, in units of one scalar multiplication on the curve at a few thousand bits: the twists, the numerical computation of the class polynomials of the class field tower (cheap with Weber's function, which is usable for even D and, through the order of conductor 2, for odd D when the v of 4n = t^2 + |D| v^2 is even, as veven says), and the descent through the prime factors p of h (a square root for p = 2, radicals or a small powering for p = 3, a p-th root or a powering of a degree p polynomial otherwise), or the cost of a root of the genus field factor if that is smaller. ecpp_disc_cost_n uses n modulo 5, 7, 11 and 13 (nmodp, or the average over n if NULL) and scales the cost of the class polynomial numerics, which does not depend on n, to the bit size of n. ecpp_disc_cost is the optimistic estimate (with veven = 1) used to order and admit the pool. Class numbers with a prime factor above 13 get a cost above ECPP_DISC_COST_MAX.

Returns whether the class field tower is the cheaper way to a curve for d (class number at least 2, and Weber's function usable or h \le 48), and sets Dt to the discriminant to build the tower on (D, or 4D for odd D with veven set).

Given D < 0, an odd n with \gcd(n, D) = 1 and a square root of D modulo n, finds t, v \ge 0 with t^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]).

Set j to a root modulo the prime modulus n of ctx of the Hilbert class polynomial H_D, for a fundamental discriminant D such that n splits completely in the Hilbert class field (that is, 4n = t^2 + |D| v^2), through the class field tower of Enge and Morain [EngeMorain2003]. Return 1 on success and 0 on failure. The flags of the underscore version are ECPP_TOWER_KUMMER (compute the Kummer data, which ecpp_class_poly_tower does from ECPP_KUMMER_BITS bits) and ECPP_TOWER_J (use j rather than Weber's function).

Sets F to the factor of the Hilbert class polynomial H_D modulo n (the modulus of ctx) that corresponds to the principal genus. Here D = p_1^* \cdots p_g^* with the p_i^* given in pstar (the signed odd primes p^* = (-1)^{(p-1)/2} p dividing D and, for even D, the factor q_0 \in \{-4, 8, -8\}), and sqrts[i] is a square root of pstar[i] modulo n, which must exist. Over the genus field K(\sqrt{p_1^*}, \ldots, \sqrt{p_g^*}), H_D factors into 2^{g-1} conjugate factors of degree h(D)/2^{g-1}, whose coefficients are identified numerically from the values of j at the reduced forms grouped by genus; F is the image of one of them modulo n, so that finding a root costs a fraction 2^{-(g-1)} of a root of H_D. Returns 1 on success and 0 if g < 2 or the coefficients could not be identified. Requires D fundamental.

Sets x to a root of the monic polynomial f of degree 2, 3 or 4, assumed to split completely modulo the prime modulus n of ctx, by radicals (Cardano, Ferrari): a few square and cube roots modulo n, some ten times cheaper than a powering of a polynomial modulo f. Degrees 3 and 4 require n \equiv 1 \pmod 3. Returns 1 on success and 0 if the degree or n is not handled or the computation failed.

Sets x to a root of the monic polynomial f, assumed to split completely modulo the prime modulus of ctx: by radicals when possible, and otherwise by random splitting with \gcd(f, (x + r)^{(n-1)/2} - 1). Returns 1 on success and 0 otherwise.