paul zimmermann <paul.zimmerm...@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.
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
