On 2023-07-09 20:12, herm...@stamm-wilbrandt.de wrote:
But the number I am really interested in (largest known prime "=1 (mod
4)", rank 9: https://t5k.org/primes/lists/all.txt)
8 2^32582657-1 9808358 G9 2006 Mersenne 44
9 10223*2^31172165+1 9383761 SB12 2016
10 2^30402457-1 9152052 G9 2005 Mersenne 43
would take roughly 80 days to compute sqrtm1 (above "powm()")
sequentially with 7600X ...
? f(9383761)/3600
%13 = 1914.8802571909706918476056601972222222
? f(9383761)/3600/24
%14 = 79.786677382957112160316902508217592593
?
Any other ideas on speeding up "powm(_, qnr, p/4, p)" with millions
digits prime p somehow?
The runtime forecast was a bit coarse based on double logarithmic
quadratic regression of up to 1,000,000-digit primes runtimes.
I enhanced sqrtm1.cc allowing to get a better runtime forecast:
https://github.com/Hermann-SW/RSA_numbers_factored/blob/main/c%2B%2B/sqrtm1.cc
hermann@7600x:~/RSA_numbers_factored/c++$ ./sqrtm1
Format: ./sqrtm1 i [div] with 0<=i<=8 or i>8, div>=1
hermann@7600x:~/RSA_numbers_factored/c++$
Instead of computing "a^1,000,000 (mod p)", for detrmmining the coarse
runtime I determined runtime to compute "powm(_, a, 100, p)" and
multiplied it by 10,000 as an upper bound (because "(a^100 (mod
p))^10,000 (modp)" is same value).
In this posting I showed that small factors m of prime "m*2^l+1",
computation time besides computing the powers of 2 with very large "l"
nearly take no time:
https://pari.math.u-bordeaux.fr/archives/pari-users-2307/msg00026.html
So for the nearly 32million bit prime I am interested in I started with
divider 1million and got a coarse upper bound of 87.27 days in quick
time:
hermann@7600x:~/RSA_numbers_factored/c++$ ./sqrtm1 8 1000000
9383761-digit prime p (31172179 bits)
smallest quadratic non-residue prime: 3
7.74048s (87.27 days)
done
hermann@7600x:~/RSA_numbers_factored/c++$
Then I reduced divider by factors 3.333 and 3 repeatedly, getting a much
better upper bound of 74.13 days in 11minutes, see below. That method
computes "powm()" on target CPU, giving real measurements.
I ordered a USV to secure such long computation of 7600X OC if I cannot
find a faster way to determine "sqrt(-1) (mod p)" via "powm(_, qnr, p/4,
p)" for the 9383761-digit prime p (in addition likely to compute 1day
long smaller powers repeatedly as described, and logging them just in
case computation has to be restarted).
hermann@7600x:~/RSA_numbers_factored/c++$ ./sqrtm1 8 300000
9383761-digit prime p (31172179 bits)
smallest quadratic non-residue prime: 3
23.2467s (80.65 days)
done
hermann@7600x:~/RSA_numbers_factored/c++$ ./sqrtm1 8 100000
9383761-digit prime p (31172179 bits)
smallest quadratic non-residue prime: 3
66.1781s (76.53 days)
done
hermann@7600x:~/RSA_numbers_factored/c++$ ./sqrtm1 8 30000
9383761-digit prime p (31172179 bits)
smallest quadratic non-residue prime: 3
220.068s (76.34 days)
done
hermann@7600x:~/RSA_numbers_factored/c++$ ./sqrtm1 8 10000
9383761-digit prime p (31172179 bits)
smallest quadratic non-residue prime: 3
640.685s (74.13 days)
done
hermann@7600x:~/RSA_numbers_factored/c++$
Regards,
Hermann.
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
