hermann on Thu, 06 Jul 2023 21:34:32 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

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



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.