Jacobi symbol using Lehmer's algorithm.

[Niels Möller]

nisse at lysator.liu.se (Niels Möller) writes:

> New version (the file is getting rather large now) at
> http://www.lysator.liu.se/~nisse/misc/jacobi.c

And here's a benchmark on shell:

n             old lehmer subquadratic
   10      13.118  0.600        0.577
   30      31.861  0.471        0.467
  100     441.870  0.288        0.288
  300    3310.419  0.180        0.180
 1000   36827.000  0.121        0.099
 3000  300266.000  0.118        0.058
10000 3564051.000  0.103        0.029

So at 10000 limbs, the Lehmer code beats the old code by 10 times, and
then the subquadratic algorithm wins a factor 3.4 more.

Regards,
/Niels

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