## An *O(M(n)* log *n)* Algorithm for the Jacobi Symbol

236. R. P. Brent and
Paul Zimmermann,
An *O(M(n)* log *n)* algorithm for the Jacobi symbol,
* Proc. ANTS-IX*
(Nancy, 19-23 July 2010),
*Lecture Notes in Computer Science*, Vol. 6197,
Springer-Verlag, 2010, 83-95.
arXiv:1004.2091v2
Preprint:
pdf (172K).

## Abstract

The best known algorithm to compute the Jacobi symbol of two
*n*-bit integers
runs in time *O(M(n)* log *n)*,
using Schönhage's fast continued fraction
algorithm combined with an identity due to Gauss. We give a different
*O(M(n)* log *n)* algorithm
based on the binary recursive gcd algorithm of
Stehlé and Zimmermann.
Our implementation, which to our knowledge is the first to run in
time *O(M(n)* log *n)*,
is faster than GMP's quadratic implementation for
inputs larger than about 10000 decimal digits.

## Remarks

The subquadratic code for computing the Jacobi symbol as described in
the paper is
available here.
Go to next publication

Return to Richard Brent's index page