See
https://github.com/gerbicz/CM/blob/main/corn.c .
The original code for Cornacchia just called Pari-Gp.
At 8k digits my Cornacchia code is 5.8 times faster, and for larger N it could be even faster.
Original code on approx 8k digits input (N=10^8007+21) using 4 physical cores, without gwnum library:
Code:
-- Size [0]: 26599 bits
Time for discriminant -1642404: 470.9 (159.5)
largest prime of d: 97
largest prime of h: 5
discriminants: 1.9 (1.9)
54 qroot: 86.3 (29.3)
57684 Cornacchia: 184.4 (62.4)
1644 trial div: 46.0 (11.5)
90 is_prime: 152.4 (54.4)
-- Size [1]: 26529 bits
Time for discriminant -6487771: 1707.2 (575.7)
largest prime of d: 907
largest prime of h: 13
discriminants: 2.0 (2.0)
156 qroot: 255.6 (86.5)
150518 Cornacchia: 479.9 (161.7)
3236 trial div: 90.8 (22.8)
816 is_prime: 1349.8 (462.3)
Using my own code:
Code:
-- Size [0]: 26599 bits
Time for discriminant -1642404: 319.8 (108.5)
largest prime of d: 97
largest prime of h: 5
discriminants: 1.9 (1.9)
54 qroot: 86.4 (29.3)
57684 Cornacchia: 32.9 (11.2)
1644 trial div: 46.1 (11.6)
90 is_prime: 152.5 (54.6)
-- Size [1]: 26529 bits
Time for discriminant -6487771: 1459.2 (493.8)
largest prime of d: 907
largest prime of h: 13
discriminants: 2.0 (2.0)
156 qroot: 254.5 (86.2)
150518 Cornacchia: 81.7 (27.7)
3236 trial div: 91.0 (22.9)
816 is_prime: 1349.8 (463.5)
Use gmp's half gcd code, do constant number of Euclidean algorithm's steps on the top limbs in constant time(!),
then do several mod tricks/quadratic residue tests to decrease the further computations.
More in the code, probably this time I have over commented. Used my own Legendre symbol code, it is also faster than the built-in kronecker. (calling it only for (k/n), when n is prime, so Legendre=kronecker).
Pointless to test it below 2^512, since it falls back to the original code. Also it is worth to see
the so called second step in the ecpp [I had code that failed in that part, since not saved V in the 1st step].
To compile: maybe it would work without any problem, for me the process:
On lib folder's pari.c replace the bool cm_pari_cornacchia function() with my code.
./configure --enable-mpi
On lib folder's makefile at the 263th line add to that line -I/home/gerbicz/gmp-6.2.1 -L/home/gerbicz/gmp-6.2.1
use your installed gmp's folder name. (this line was for the CFLAGS).
make install