Dartmouth logo Dartmouth College Computer Science
Technical Report series
CS home
TR home
TR search TR listserv
By author: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
By number: 2017, 2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001, 2000, 1999, 1998, 1997, 1996, 1995, 1994, 1993, 1992, 1991, 1990, 1989, 1988, 1987, 1986

On the Worst Case of Three Algorithms for Computing the Jacobi Symbol
Jeffrey Shallit
Dartmouth PCS-TR89-140

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).


PDF PDF (592KB)

Bibliographic citation for this report: [plain text] [BIB] [BibTeX] [Refer]

Or copy and paste:
   Jeffrey Shallit, "On the Worst Case of Three Algorithms for Computing the Jacobi Symbol." Dartmouth Computer Science Technical Report PCS-TR89-140, 1989.


Notify me about new tech reports.

Search the technical reports.

To receive paper copy of a report, by mail, send your address and the TR number to reports AT cs.dartmouth.edu


Copyright notice: The documents contained in this server are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Technical reports collection maintained by David Kotz.