# Jacobi symbol using Lehmer's algorithm.

Niels Möller nisse at lysator.liu.se
Mon Jan 25 10:50:51 CET 2010

```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.
```