FYI: 75 days sequential computation started [compute sqrt(-1) (mod p) for 9,383,761-digit prime]

hermann at stamm-wilbrandt.de hermann at stamm-wilbrandt.de
Thu Jul 20 22:23:51 CEST 2023


Code, description, motivation, ... is all in this repo:
https://github.com/Hermann-SW/9383761-digit-prime

README.md has these sections:
## Build and install
## Motivation
## Why 7600X CPU?
## *sqrt(-1) (mod p)* for 9,383,761-digit prime p
## Previous runtimes for up to 1,000,000-digit primes
## Upper bound on 70+ days computation
## Basement ceiling computing center for 70+ days
## TEST
## 75 days sequential computation
## Power consumption

I asked on speeding up computation of "mpz_powm(res, 3, 2^large, p)" 
before on this list
https://gmplib.org/list-archives/gmp-devel/2023-July/006187.html

and on pari-user
https://pari.math.u-bordeaux.fr/archives/pari-users-2307/msg00026.html

and the responses indicated that "large" many squarings (mod p) will 
have to be done sequentially.

For the 75 days computation,  large = 31,172,163  ;-)

31,172,163 == 11121 * 2803
Computation does 11121 loops, with each loop computing "mpz_powm(a, b, 
2^2803, p); b=a" in 589s and storing the result. Without deleting files 
100GB disk space is needed. I plan to keep the 11121 different power of 
2 exponent results, because that will allow me to compute any other 
power of 2 exponent of 3 (mod p) in less than 10min. I have no idea yet 
whether there is any need to be able for that.


Regards,

Hermann.


More information about the gmp-devel mailing list