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) ? |
This question becomes more important, the larger prime numbers are tried.Are there any alternative ways to determine say sum of squares for largest twin prime with significantly faster than 3h runtime for that CPU?
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.jpgAfter 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 GroupPARI/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-valuesBiggest 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.