Fast libgmpxx and libpari computations on 9,383,761-digit biggest known prime p that is =1 (mod 4)

hermann at hermann at
Sun Aug 6 16:01:10 CEST 2023

I determined "sqrt(-1) (mod p)" for that prime p, rank 10 of largest 
known primes list

  rank  description                     digits   who   year comment
-----  ------------------------------- -------- ----- ---- 
    10  10223*2^31172165+1               9383761 SB12  2016

in 13.2h with llr tool with 24 threads:

 From that I determined unique sum of squares of p=x^2+y^2.
The 4,691,881- and 4,691,880-digit numbers x and y are defined in C++ 

by just mpz_class without issues:
     mpz_class x("223757 ... 534644");
     mpz_class y("236151 ... 476249");

That demo code starts with x,y and p and computes sqrtm1 from that in 
only 4.23s (i7-11850H CPU).
Then it uses libpari "halfgcdii()" function to compute x and y from just 
sqrtm1 and p in 3.72s.
Computing x,y from sqrtm1 is possible with gaussian integer gcd, but 
that is orders of magnitude slower than using "halfgcdii()".
All intermediate results are verified with asserts.

$ f=sqrtm1.9383761_digit.largest_known_1mod4_prime
$ g++ $ -lgmp -lgmpxx -O3 -o $f -lpari -DPARI
$ ./$f
a = y^(-1) (mod p) [powm]; a *= x; a %= p
[M,V] = halfgcdii(sqrtm1, p)
[x,y] = [V[2], M[2,1]]

Nice that such fast computations for more than 31million bit numbers are 
possible with libgmpxx.



More information about the gmp-discuss mailing list