Re: What happened to "Modexp, bᵈ mod m" topic from (last updted 2016) "Itemised plans for GMP"

[hermann at stamm-wilbrandt.de]

On 2023-07-09 20:12, hermann at 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 at 7600x:~/RSA_numbers_factored/c++$ ./sqrtm1
Format: ./sqrtm1 i [div]  with 0<=i<=8 or i>8, div>=1
hermann at 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 at 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 at 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 at 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 at 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 at 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 at 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 at 7600x:~/RSA_numbers_factored/c++$


Regards,

Hermann.