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

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

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

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:
 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;
+        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(!):

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:
- 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

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

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:

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?