Re: Abnormous memory use for gaussian gcd()?

[hermann@stamm-wilbrandt.de]

On 2023-06-07 08:35, hermann@stamm-wilbrandt.de wrote:
> ...
> 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!
I did runtime evaluation for the conversions between sum of squares and 
sqrt(-1) (mod p).
This time for biggest known twin prime (388342-digits or 1,290,000 
bits):
https://github.com/Hermann-SW/RSA_numbers_factored/blob/main/pari/sqrtm1_qfbcornacchia.biggest_twin_prime.gp

Since sqrtm1 variable gets assigned directly, the whole script finishes 
nearly immediately.

Output for i7-11850H CPU:

388342-digit prime p
[M,V] = halfgcd(sqrtm1, p)
  ***   last result: cpu time 61 ms, real time 61 ms.
[x,y] = [V[2], M[2,1]]
  ***   last result: cpu time 0 ms, real time 0 ms.
sqrtm1 = lift(Mod(x/y, p))
  ***   last result: cpu time 123 ms, real time 123 ms.
done
Goodbye!

Screenshot of new diagram (3:04h for one powm(rnd, p/4, p) try, no 
runtime determined for qfbcornacchia() yet):
https://stamm-wilbrandt.de/images/388342-digits_prime.png
Shortened GraphvizFiddle share link:
https://stamm-wilbrandt.de/388342-digit_prime.html


Since runtime is so short, I executed that on Cortex A72 CPU of my 
Raspberry Pi400:

pi@pi400-64:~/RSA_numbers_factored/pari $ gp-2.16 < 
sqrtm1_qfbcornacchia.biggest_twin_prime.gp
...
parisizemax = 3000000512, primelimit = 1048576, nbthreads = 4
388342-digit prime p
[M,V] = halfgcd(sqrtm1, p)
  ***   last result: cpu time 336 ms, real time 336 ms.
[x,y] = [V[2], M[2,1]]
  ***   last result: cpu time 1 ms, real time 1 ms.
sqrtm1 = lift(Mod(x/y, p))
  ***   last result: cpu time 679 ms, real time 681 ms.
done
Goodbye!
pi@pi400-64:~/RSA_numbers_factored/pari $


For any clue on how to determime either sqrtm1 or [x,y] in significantly 
less than 3 hours for biggest twin prime I would be very grateful.

Regards,

Hermann Stamm-Wilbrandt.