Sprezzatech: Expert UNIX/HPC consulting and custom development.
Stehlé-Zimmermann algorithm
From blackwiki
An algorithm for calculating the Jacobi symbol of two n-digit numbers in O(lg n M(n)) time, where M(n) is the complexity of a chosen multiplication algorithm for n-bit numbers.
See Also
- "An O(M(n) log n)) Algorithm for Calculating the Jacobi Symbol", Brent and Zimmerman, 2010