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

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

2010-04-13

arxiv.org/abs/1004.2091v2

Proc. ANTS-IX (Nancy, 19-23 July 2010), Lecture Notes in Computer Science, Vol. 6197, Springer-Verlag, 2010, 83-95

Computer Science

Data Structures and Algorithms

Submitted to ANTS IX (Nancy, July 2010)

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

An O(M(n) log n) algorithm for the Jacobi symbol does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An O(M(n) log n) algorithm for the Jacobi symbol, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An O(M(n) log n) algorithm for the Jacobi symbol will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-280651