Re: 388342-digit largest known twin prime: faster sum of squares or sqrt(-1) (mod p) ?

[hermann@stamm-wilbrandt.de]

> Are there any alternative ways to determine say sum of squares for
> largest twin prime with significantly faster than 3h runtime for that
> CPU?
This question becomes more important, the larger prime numbers are 
tried.


On the weekend I tried smallest known 1,000,000-digit prime, rank 2137 
on this list:
https://t5k.org/primes/lists/all.txt
...
 2137  10^999999+308267*10^292000+1     1000000 CH10  2021
...

It is much easier to add such formulas in Pari/GP or Python, looks a bit 
ugly in C++:
...
     unsigned u = atoi(argv[1]);
-    assert(u >= 0 && u < 7);
+    assert(u >= 0 && u < 8);

     switch (u) {
         case 0: {
@@ -65,6 +65,14 @@ int main(int argc, char *argv[]) {
             a += r[u].a;
             break;
         }
+        case 7: {
+            mpz_ui_pow_ui(a.get_mpz_t(), 10, 999999);
+            mpz_ui_pow_ui(b.get_mpz_t(), 10, 292000);
+            b *= mpz_class("308267");
+            a += b;
+            a += 1;
+            break;
+        }
         default:  assert(0 || !"wrong selection (0-6)");
...

I started run two nights ago, last night it completed after 
26:00:41h(!):
https://stamm-wilbrandt.de/images/20230612_065957.15pc.jpg

After reboot, without GUI on that i7-11850H Linux laptop, in console a 
single process did run to reach up to 4.8GHz boost CPU frequency 
(i7-11850H is a 2.5GHz CPU). Over the 26 hours I used a 2nd console 
window to query current CPU frequency few times. What I saw was around 
4.4GHz for sqrtm1 process:
cat /sys/devices/system/cpu/cpu?/cpufreq/scaling_cur_freq


This is reduced diagram:
https://stamm-wilbrandt.de/images/sqrtm1.smallest_known_1million_digit_prime.gp.png
- 1ms to determine smallest quadratic nonresidue for that prime (13)
- 26:00:41h to determine sqrtm1 with libgmpxx "powm()"
- 217ms(!) to compute "halfgcd()" for sum of squares determination
- 439ms to compute "lift(Mod(x/y, p)=" to compute sqrtm1 from sum of 
squares

stammw:pari$ gp-2.16 < sqrtm1.smallest_known_1million_digit_prime.gp
Reading GPRC: /etc/gprc
GPRC Done.

        GP/PARI CALCULATOR Version 2.16.1 (development 28569-63935bc03)
          amd64 running linux (x86-64/GMP-6.1.2 kernel) 64-bit version
            compiled: Jun  6 2023, gcc version 8.5.0 20210514 (GCC)
                           threading engine: pthread
                (readline v7.0 disabled, extended help enabled)

                     Copyright (C) 2000-2023 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and 
comes
WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?18 for how to get moral (and possibly technical) support.

parisizemax = 2000003072, primelimit = 1048576, nbthreads = 8
1000000-digit prime p (3321925 bits)
[M,V] = halfgcd(sqrtm1, p)
  ***   last result: cpu time 217 ms, real time 218 ms.
[x,y] = [V[2], M[2,1]]
  ***   last result: cpu time 0 ms, real time 0 ms.
sqrtm1 = lift(Mod(x/y, p))
  ***   last result: cpu time 439 ms, real time 442 ms.
done, all asserts OK
Goodbye!
stammw:pari$



I created new quadratic regression diagram with two curves. This time 
with identical curves, one with 5 primes in range 100355..388342, the 
other with additional grey data point (1000000, 93640.8). As can be seen 
the curves are nearly identical:
https://github.com/Hermann-SW/QuadraticRegression#same-curves-vizualize-effect-of-additional-values


Biggest known prime 2^82589933-1 has 24,862,048 decimal digits, but it 
is =3 (mod 4).

Biggest known prime =1 (mod 4) has rank 9 with 9,383,761-digits 
(10223*2^31172165+1).

Extrapolating runtime for that prime with curve corrected for 
1000000-digit prime says, that more than 106 days with i7-11850H CPU at 
boost CPU frequency of up to 4.8GHz are needed to compute sqrtm1 for 
that prime.


Any thoughts on speeding up "powm()" or "Mod(sqnr^(p/4), p)"?
Or another way to compute sqrtm1 other than slower "lift(sqrt(Mod(-1, 
p)))" to compute sqrt1, or even slower "qfbcornacchia(1, p)" to compute 
sum of squares?


Regards,

Hermann.