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

[hermann@stamm-wilbrandt.de]

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.