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

I put up a new version at thhe same place. Now uses a more compact
representation of the state, and as a result the lookup table is reduced
from 512 bytes to 208.

It could quite easily be halved again to 104 bytes (don't treat the old
and new sign bit as input and output of the table lookup, instead use an
output bit to say if the sign should be flipped). But that would make
the update slightly more expensive, I think, something like three
instrructions rather than 1 on x86.

Regards,
/Niels

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