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