patch for speed

[Niels Möller]

paul zimmermann <Paul.Zimmermann at inria.fr> writes:

>        Niels,
>
>> Wouldn't that patch call mpz_legendre (a, p) with p not prime? Which is
>> invalid, but kind-of works *because* mpz_legendre is an alias for
>> mpz_jacobi.
>
> good point. Do you want a new patch which ensures p is an odd positive prime?

I'd like to understand the benefits of ./speed mpz_legendre first, since
I don't really see any. Currently, it's an alias for mpz_jacobi, and I'm
not aware of any concrete plans to change that.

One could consider computing the legendre symbol with modular
exponentiation, which is asymptotically slower but potentially faster
for some smallish sizes. But at the moment, mpz_powm is at best 7 times
slower than mpz_jacobi, for size n = 3, when I try it on my closest
machine.

$ ./tune/speed -c -s 1-10 -r mpz_jacobi mpz_powm 
overhead 4.68 cycles, precision 10000 units of 1.13e-09 secs, CPU freq
884.86 MHz
           mpz_jacobi      mpz_powm
1             #699.45       14.8460
2            #1481.50       11.8880
3            #4512.19        7.1814
4            #6352.69        9.1231
5            #8173.88        9.3008
6           #10050.12        8.9304
7           #11914.19        9.1968
8           #13811.12       10.1785
9           #15741.36       11.3230
10          #17467.37       12.0439

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.