Skip navigation
Skip navigation

An O(M (n) log n) Algorithm for the Jacobi Symbol

Brent, Richard; Zimmermann, Paul


The best known algorithm to compute the Jacobi symbol of two n-bit integers runs in time O(M(n)logn), using Schönhage's fast continued fraction algorithm combined with an identity due to Gauss. We give a different O(M(n)logn) algorithm based on the binar

CollectionsANU Research Publications
Date published: 2010
Type: Conference paper
Source: Algorithmic Number Theory
DOI: 10.1007/978-3-642-14518-6_10


File Description SizeFormat Image
01_Brent_An_O(M_(n)_log_n)_Algorithm_2010.pdf243.35 kBAdobe PDFThumbnail

Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  17 November 2022/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator