hermann on Wed, 07 Jun 2023 08:40:21 +0200

 Re: Abnormous memory use for gaussian gcd()?

```...
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
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.

```