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

Richard P. Brent; Paul Zimmermann

doi:10.1007/978-3-642-14518-6_10

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

Richard P. Brent, Paul Zimmermann

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › peer-review

14 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	Algorithmic Number Theory - 9th International Symposium, ANTS-IX, Proceedings
Pages	83-95
Number of pages	13
DOIs	https://doi.org/10.1007/978-3-642-14518-6_10
Publication status	Published - 2010
Event	9th International Symposium on Algorithmic Number Theory, ANTS-IX - Nancy, France Duration: 19 Jul 2010 → 23 Jul 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6197 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	9th International Symposium on Algorithmic Number Theory, ANTS-IX
Country/Territory	France
City	Nancy
Period	19/07/10 → 23/07/10

Access to Document

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

Cite this

Brent, R. P., & Zimmermann, P. (2010). An O(M(n) log n) algorithm for the Jacobi symbol. In Algorithmic Number Theory - 9th International Symposium, ANTS-IX, Proceedings (pp. 83-95). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6197 LNCS). https://doi.org/10.1007/978-3-642-14518-6_10

@inproceedings{6a9d1efb024f4649b1735fb6f45d3106,

title = "An O(M(n) log n) algorithm for the Jacobi symbol",

abstract = "The best known algorithm to compute the Jacobi symbol of two n-bit integers runs in time O(M(n)logn), using Sch{\"o}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{\'e} 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.",

author = "Brent, \{Richard P.\} and Paul Zimmermann",

year = "2010",

doi = "10.1007/978-3-642-14518-6\_10",

language = "English",

isbn = "3642145175",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "83--95",

booktitle = "Algorithmic Number Theory - 9th International Symposium, ANTS-IX, Proceedings",

note = "9th International Symposium on Algorithmic Number Theory, ANTS-IX ; Conference date: 19-07-2010 Through 23-07-2010",

}

Brent, RP & Zimmermann, P 2010, An O(M(n) log n) algorithm for the Jacobi symbol. in Algorithmic Number Theory - 9th International Symposium, ANTS-IX, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6197 LNCS, pp. 83-95, 9th International Symposium on Algorithmic Number Theory, ANTS-IX, Nancy, France, 19/07/10. https://doi.org/10.1007/978-3-642-14518-6_10

An O(M(n) log n) algorithm for the Jacobi symbol. / Brent, Richard P.; Zimmermann, Paul.
Algorithmic Number Theory - 9th International Symposium, ANTS-IX, Proceedings. 2010. p. 83-95 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6197 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › peer-review

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 - https://www.scopus.com/pages/publications/77955333046

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

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

M3 - Conference Paper

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 -

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

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this