An O(M(n) log n) algorithm for the Jacobi symbol - Archive ouverte HAL Access content directly
Conference Papers Year : 2010

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

(1) , (2)
1
2

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.

Dates and versions

inria-00447968 , version 1 (18-01-2010)

Identifiers

Cite

Richard P. Brent, Paul Zimmermann. An O(M(n) log n) algorithm for the Jacobi symbol. 9th Algorithmic Number Theory Symposium - ANTS IX, Jul 2010, Nancy, France. pp.83-95, ⟨10.1007/978-3-642-14518-6_10⟩. ⟨inria-00447968⟩
98 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More