Karim Belabas on Wed, 07 Jun 2023 19:49:17 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Abnormous memory use for gaussian gcd()? 

* Bill Allombert [2023-06-07 18:44]:
[...]
> 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.

We use a proven formula for optimality of Cipolla wrt Tonelli-Shanks,
but there's a catch: it only proves optimality for given prime p when
averaging over all quadratic residues. It says nothing about a given
input.

It so happens that sqrt(-1) is always faster using Tonelli-Shanks
rather than Cipolla. In fact, Bill's variant raising a quadratic non
residue to the appropriate power will be a little faster.

It's very easy to fix for -1 (an important special case !), but
arbitrary elements of the 2-Sylow of (F_p^*)^2 can be similarly accelerated,
although it becomes non trivial to test it ( I don't see anything better
than taking at most v_2(p - 1) - 1 successive squares, stopping whenever the
result is -1 ).

Cheers,

    K.B.
-- 
Pr. Karim Belabas, U. Bordeaux, Vice-président en charge du Numérique
Institut de Mathématiques de Bordeaux UMR 5251 - (+33) 05 40 00 29 77
http://www.math.u-bordeaux.fr/~kbelabas/