Jacobi symbol using Lehmer's algorithm.

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> There seem to be a correlation between you saying "I don't have time for
> X" and your immediate quality implementation of X.  :-)

It turned out to be a little easier than I expected ;-)

The subquadratic thing should be just a few hours of additional work.

Some issues to think about if/when this code is integrated properly in
GMP:

1. How can we avoid large amounts of code duplication with the gcd
   code? At the moment, I'm more concerned with source code than object
   code. One could do things like

     hgcd2_jacobi.c:

     #define QUOTIENT_UPDATE ...
     #include "hgcd2.c"

   and for the functions handling large numbers one might pass around
   function pointers. E.g., a single subquadratic hgcd function which
   calls a basecase function via a pointer. The older version of the
   subquadratic gcd code with its quotient stack did something similar
   to that, I think.

2. Would it be useful with a function which returns both the gcd and the
   Jacobi symbol? I.e., compute the jacobi symbol, and in case it is
   zero, also return the non-trivial common factor, which is free except
   for the coping of the returned value? I don't really know what the
   jacobi symbol computation is used for... Would gcdext + jacobi make
   more or less sense than gcd + jacobi?

>   I have special code for the small cases n = 1 and 2 (which it might
>   be better to rewrite using the binary algorithm)
>   
> There is some small cases code in the old jacobi code too.

The only somewhat tricky part if we want to switch to a binary algorithm
or small sizes is to translate the current state of the left-to-right
algorithm to the correct inputs for the binary algorithm.

> Really impressive speedups!  For huge operands, the new code is about
> 10x faster than the old code.

I guess that's the expected order of magnitude when comparing Euclid to
Lehmer? Although the old Jacobi code uses a basic binary algorithm
rather than Euclid. What matters for the coefficient of the quadratic
term is the amount of progress per bignum operation.

Regards,
/Niels

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