An O(M(n) log n) Algorithm for the Jacobi Symbol
236. R. P. Brent and
An O(M(n) log n) algorithm for the Jacobi symbol,
(Nancy, 19-23 July 2010),
Lecture Notes in Computer Science, Vol. 6197,
Springer-Verlag, 2010, 83-95.
The best known algorithm to compute the Jacobi symbol of two
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.
The subquadratic code for computing the Jacobi symbol as described in
the paper is
Go to next publication
Return to Richard Brent's index page