Jacobi Symbol

[Niels Möller]

paul zimmermann <Paul.Zimmermann at inria.fr> writes:

> since GMP 5.1.0, i.e., 8 versions of GMP, the documentation says:
>
>    15.3.5 Jacobi Symbol
>    --------------------
>
>    [This section is obsolete.  The current Jacobi code actually uses a very
>    efficient algorithm.]
>
> I just checked the latest daily snapshot, it is still the same.
>
> When will this section be updated?

I'm attaching my draft paper explaining the algorithm used in GMP. This
was written back in 2010, do you know if the algorithm has been
published elsewhere in the meantime? The trick (i.e., using part (v) and
(vi) of Proposition 1) dates back at least to work by Schönhage in the
80s, and I implemented it after it was explained to me by Richard Brent.

For the GMP manual, ideally there should be a brief description and a
pointer to a published book or paper.

Regards,
/Niels

-------------- next part --------------
A non-text attachment was scrubbed...
Name: jacobi.pdf
Type: application/pdf
Size: 245069 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-bugs/attachments/20170821/bfac90c6/attachment-0001.pdf>
-------------- next part --------------

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