TY - GEN

T1 - An O(M(n) log n) algorithm for the Jacobi symbol

AU - Brent, Richard P.

AU - Zimmermann, Paul

PY - 2010

Y1 - 2010

N2 - The best known algorithm to compute the Jacobi symbol of two n-bit integers runs in time O(M(n)logn), using Schönhage's fast continued fraction algorithm combined with an identity due to Gauss. We give a different O(M(n)logn) 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)logn) - is faster than GMP's quadratic implementation for inputs larger than about 10000 decimal digits.

AB - The best known algorithm to compute the Jacobi symbol of two n-bit integers runs in time O(M(n)logn), using Schönhage's fast continued fraction algorithm combined with an identity due to Gauss. We give a different O(M(n)logn) 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)logn) - is faster than GMP's quadratic implementation for inputs larger than about 10000 decimal digits.

UR - http://www.scopus.com/inward/record.url?scp=77955333046&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-14518-6_10

DO - 10.1007/978-3-642-14518-6_10

M3 - Conference contribution

SN - 3642145175

SN - 9783642145179

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 83

EP - 95

BT - Algorithmic Number Theory - 9th International Symposium, ANTS-IX, Proceedings

T2 - 9th International Symposium on Algorithmic Number Theory, ANTS-IX

Y2 - 19 July 2010 through 23 July 2010

ER -