Re: Abnormous memory use for gaussian gcd()?

[hermann@stamm-wilbrandt.de]

> > ...
> > That is so cool, with your gcd() fix halgcd() became even faster!
>
> Indeed, the master branch includes several changes to speed up halfgcd.
> However they predate the change to gcd which is unrelated.
>
> But what I do not quite understand is how do you get the squareroots.
> If you need to compute them, you can as well use qfbcornacchia 
> directly.
> (once you have a solution a^2+b^2=p, you can recover the square root
> with a/b mod p).
OK, I did comparison of computing "sqrt(-1) mod p" first versus 
"qfbcornacchia()" first:
https://github.com/Hermann-SW/RSA_numbers_factored/blob/main/pari/sqrtm1_qfbcornacchia.gp

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 added very slow Python "diop_DN(-1, 
p)", that is no
option runtime wise.

Screenshot:
https://stamm-wilbrandt.de/images/100355-digits_prime.png
GraphvizFiddle share link:
https://stamm-wilbrandt.de/100355-digit_prime.html

Output of "gp-2.16 < sqrtm1_qfbcornacchia.gp" for 
10000-/36401-/100355-digit primes.
qfbcornacchia() is slightly slower on i7-11850H for < 100355-digit 
primes, a bit
faster for 100355-digit prime:

10000-digit prime p
sqrt(Mod(-1, p))
  ***   last result: cpu time 3,153 ms, real time 3,177 ms.
  ***   last result: cpu time 1 ms, real time 1 ms.
  ***   last result: cpu time 0 ms, real time 0 ms.
qfbcornacchia(1, p)
  ***   last result: cpu time 3,181 ms, real time 3,185 ms.
  ***   last result: cpu time 1 ms, real time 1 ms.
done
Goodbye!


36401-digit prime p
sqrt(Mod(-1, p))
  ***   last result: cpu time 1min, 16,523 ms, real time 1min, 16,624 
ms.
  ***   last result: cpu time 3 ms, real time 3 ms.
  ***   last result: cpu time 0 ms, real time 0 ms.
qfbcornacchia(1, p)
  ***   last result: cpu time 1min, 19,346 ms, real time 1min, 19,417 
ms.
  ***   last result: cpu time 4 ms, real time 5 ms.
done
Goodbye!


100355-digit prime p
lift(sqrt(Mod(-1, p)))
  ***   last result: cpu time 33min, 30,436 ms, real time 33min, 32,567 
ms.
  ***   last result: cpu time 10 ms, real time 10 ms.
  ***   last result: cpu time 0 ms, real time 0 ms.
qfbcornacchia(1, p)
  ***   last result: cpu time 32min, 44,159 ms, real time 32min, 45,869 
ms.
  ***   last result: cpu time 20 ms, real time 20 ms.
done
Goodbye!


Thanks again for all the Pari/GP options seen in the diagram I learned 
from you
(halfgcd, Mod(x/y, p), ...).

Regards,

Hermann Stamm-Wilbrandt.