On the Worst Case of Three Algorithms for Computing the Jacobi Symbol

Dartmouth Technical Report PCS-TR89-140

	Jeffrey Shallit

Date:  1989

URL (PDF): <http://www.cs.dartmouth.edu/reports/TR89-140.pdf> (592KB)

Abstract:
 	We study the worst-case behavior of three iterative
 algorithms- Eisenstein's algorithm, Lebesgue's algorithm, and the
 "ordinary" Jacobi symbol algorithm - for computing the Jacobi symbol.
 Each algorithm is similar in format to the Euclidean algorithm for
 computing gcd (u,v).