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

[Max Alekseyev <maxale@gmail.com>]

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).

Regards,

Max

On Thu, Jul 6, 2023 at 3:29 PM <hermann@stamm-wilbrandt.de> wrote:

It takes 3:04h for one "powm(_, qnr, p/4, p)" computation for
388342-digit prime with C++ and libgmpxx [in order to compute "sqrt(-1)
(mod p)"]. Using Pari/GP "Mod(qnr, p\4, p)" takes 16% longer than that.

I am interested in special primes of the form "p = m*2^l+1" where m is a
small number and l is huge.

Like p in example below.

Regarding the line:
? q=qnr*v; \\ q=lift(Mod(qnr, p)^(2^v))

I chose that in order to not having to wait for more than 3h to compute
"q=lift(Mod(qnr, p)^(2^v))". The next lines demonstrate, that only that
computation is relevant, since exponentiation with m for final result
takes less than a second.

So question is:
Is there any trick/algorithm speeding up computation "Mod(q, p)^(2^v)"
that has to do significantly less than v modular squarings?


hermann@7600x:~$ gp -q
? p = 2996863034895 * 2 ^ 1290000 + 1;
? #digits(p)
388342
? e=p\4;
? v=valuation(e, 2)
1289998
? forprime(t=2,oo,if( kronecker(t, p)==-1, qnr=t; break()));
? q=qnr*v; \\ q=lift(Mod(qnr, p)^(2^v))
? Mod(q, p)^(e\(2^v));
? ##
   ***   last result computed in 200 ms.
?


Regards,

Hermann.