Re: Abnormous memory use for gaussian gcd()?

[hermann@stamm-wilbrandt.de]

On 2023-06-07 18:44, Bill Allombert wrote:
> 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.
Thank you for the libgmp powm() tests.

I did compute the powm() times for C++ with libgmpxx and Python with 
gmpy2 before. Please see bottom diagram here:
https://github.com/Hermann-SW/QuadraticRegression
My Linux i7-11850H CPU did need less than 10min for powm(rnd, p/4, p) 
for the 100355-digit prime, and more than 3h for the 388342-digit prime.

Since your runtimes are longer, what CPU did you run your tests on?


Over the night I did compute "qfbcornacchia(1, p)" for the 388342-digit 
(biggest know twin) prime, after I rebooted, without GUI in Linux 
console. Slighly less than 11h, which might be OK for that big prime 
number. Part of photo, scaled down to 30% size:
https://stamm-wilbrandt.de/images/20230608_080306.part.30pc.jpg
So the Pari/GP "qfbcornacchia(1, p)" runtime is more than 3x longer than 
one "powm()" try. Since half of the numbers in Z/pZ are quadratic 
non-residues, expected runtime for "powm()" is 2*3:04h=6:08h. Because of 
the millisecond transformations determining sum of squares and sqrtm1 
are "the same". I don't know whether "qfbcornacchia(1, p)" has expected 
runtime as well.

I used this:
$ cat 388342_qfbcornacchia.gp
assert(b, v, s) = { if(!(b), error(Str(v) Str(s))); }

p = 2996863034895 * 2 ^ 1290000 + 1;
print(#digits(p), "-digit prime p");

print("qfbcornacchia(1, p)");
[x,y] = qfbcornacchia(1, p);
##
assert(x^2 + y^2 == p, "x,y", " not sum of squares");

sqrtm1 = lift(Mod(x/y, p));
##
assert(Mod(sqrtm1^2, p) == Mod(p - 1, p), "sqrtm1", " not as needed");

print("done");
$


Regards,

Hermann Stamm-Wilbrandt.