# Difference between revisions of "Stehlé-Zimmermann algorithm"

From dankwiki

(Created page with "An algorithm for calculating the http://en.wikipedia.org/wiki/Jacobi_symbol Jacobi symbol of two n-digit numbers in O(lg n M(n)) time, where M(n) is the complexity of a chose...") |
|||

Line 1: | Line 1: | ||

− | An algorithm for calculating the | + | An algorithm for calculating the [http://en.wikipedia.org/wiki/Jacobi_symbol 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== | ==See Also== |

## Latest revision as of 20:52, 9 September 2011

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