Re: How to compute "Mod(q, p)^(2^v)" with significantly less than v modular squarings?

[hermann@stamm-wilbrandt.de]

On 2023-07-06 23:06, Max Alekseyev wrote:
> Hi Hermann,
>
> If v is large, then it's worth reducing the exponent 2^v modulo p-1 -
> like:
>
> q = lift( Mod(qnr, p)^lift(Mod(2,p-1)^v)) );
>
> Here we rely on the Fermat Little Theorem, but in general (if p is not
> prime) p-1 would need to be replaced with eulerphi(p).
Thanks.

My formulation
'... form "p = m*2^l+1" where m is a small number and l is huge.'
was a bit misleading; 2^l is huge.

Unfortunately not huge enough that (mod p-1) would make a difference:

? e=p\4;
? v=valuation(e, 2)

=> 2^v <= p\4 < p-1


I compared fastest (C++ with libgmpxx) determination times for 
i7__11850H and my new much faster 7600X CPU that is rank 18 of >3100 
CPUs on PassMark single thread performance list:
https://raw.githubusercontent.com/Hermann-SW/QuadraticRegression/master/sqrtm1___.png

The i7_11850H did take 26h to compute sqrt(-1) (mod p) for smallest 
known 1,000,000-digit prime.

7600X is expected to take only 19.2h for that.

https://github.com/Hermann-SW/QuadraticRegression/blob/master/sqrtm1___.py
pi@pi400-64:~/QuadraticRegression $ python sqrtm1___.py
y = 7.950524562496551e-08x² - 0.011528213946191843x + 914.8718066871961

? 93640.8/3600
%10 = 26.011333333333333333333333333333333333
? f(x) = 7.950524562496551e-08*x^2 - 0.011528213946191843*x + 
914.8718066871961
%11 = 
(x)->7.950524562496551e-08*x^2-0.011528213946191843*x+914.8718066871961
? f(1000000)/3600
%12 = 19.136639857072461972222222222222222222
?


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 sequentially with 7600X ...


? 93640.8/3600
%10 = 26.011333333333333333333333333333333333
? f(x) = 7.950524562496551e-08*x^2 - 0.011528213946191843*x + 
914.8718066871961
%11 = 
(x)->7.950524562496551e-08*x^2-0.011528213946191843*x+914.8718066871961
? f(1000000)/3600
%12 = 19.136639857072461972222222222222222222
?

? f(9383761)/3600
%13 = 1914.8802571909706918476056601972222222
? f(9383761)/3600/24
%14 = 79.786677382957112160316902508217592593
?


Regards,

Hermann.