Skip navigation
Skip navigation

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

Download (243.35 kB)

link to publisher version

  • Altmetric Citations

Brent, Richard; Zimmermann, Paul

Description

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
URI: http://hdl.handle.net/1885/57326
Source: Algorithmic Number Theory
DOI: 10.1007/978-3-642-14518-6_10

Download

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


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