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.