Re: Abnormous memory use for gaussian gcd()?

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Wed, Jun 07, 2023 at 08:35:38AM +0200, hermann@stamm-wilbrandt.de wrote:
> I created diagram, including (faster) libgmpxx "powm()" (take random value,
> compute
> "powm(rnd, p/4, p)", test whether its square is sqrt(-1) mod p, repeat) with
> runtime
> <10min per try and 2 tries expected. That is faster than >30min of both
> Pari/GP
> options (they are very close). 

I have made a git branch bill-gmppow where you can do
install(gmppow,GGG) to use mpz_powm

I have done some tests:
p = 65516468355 * 2 ^ 333333 + 1;
Mod(7,p)^((p-1)/4)
PARI Fp_pow:
19min, 1,255 ms
gmppow(7,(p-1)/4,p);
16min, 8,960 ms
Then I tried:
? S=sqrt(Mod(-1,p));
  ***   last result computed in 52min, 3,954 ms.
which looks like a bug.
This is due to misuses of Cipolla algorithm.
We should fix it.

A similar example, but faster to check:

? p=2^1000*5^3148+1;
? for(i=1,100,Mod(3,p)^((p-1)/4))
? ##
  ***   last result computed in 9,506 ms.
? for(i=1,100,sqrt(Mod(-1,p)))
? ##
  ***   last result computed in 25,418 ms.

Note:
To find the square root, you just need to find a small prime number l so
that kronecker(l,p)==-1 and then compute Mod(l,p)^(((p-1)/4)

Cheers,
Bill