hermann on Mon, 12 Jun 2023 15:13:29 +0200

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

```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
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)
(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.

```