On the worst case of three algorithms for computing the Jacobi symbol

DOI10.1016/S0747-7171(08)80160-5MaRDI QIDQ752075zbMATH OpenOpenAlexFDO

Authors Jeffrey Shallit

Publication date 1990

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0747-7171(08)80160-5

zbMATH Keywords

algorithmcomputation of the Jacobi symbol

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Power residues, reciprocity (11A15) Number-theoretic algorithms; complexity (11Y16)

Recommendations

• An O(M(n) logn) Algorithm for the Jacobi Symbol
• Efficient algorithms for computing the Jacobi symbol
• scientific article; zbMATH DE number 1113842
• scientific article; zbMATH DE number 919915
• Dynamical analysis of a class of Euclidean algorithms.

Cites work

• scientific article; zbMATH DE number 3869411 (Why is no real title available?)
• scientific article; zbMATH DE number 4108845 (Why is no real title available?)
• scientific article; zbMATH DE number 3767785 (Why is no real title available?)
• scientific article; zbMATH DE number 3528300 (Why is no real title available?)
• scientific article; zbMATH DE number 3573943 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• scientific article; zbMATH DE number 3335208 (Why is no real title available?)
• scientific article; zbMATH DE number 3336026 (Why is no real title available?)
• A modification of the RSA public-key encryption procedure (Corresp.)
• Computational problems associated with Racah algebra
• Erratum: A Fast Monte-Carlo Test for Primality
• Fast computation of continued fraction expansions.
• On a theorem of Heilbronn
• Prime numbers and computer methods for factorization
• The Jacobi symbol algorithm
• Über die Schrittanzahl beim Algorithmus von Harris und dem nach nächsten Ganzen
• Über die mittlere Schrittanzahl bei Divisionsalgorithmen

Cited in

(5)

• scientific article; zbMATH DE number 1113842 (Why is no real title available?)
• Computations of class numbers of real quadratic fields
• Comments on search procedures for primitive roots
• Dynamical analysis of a class of Euclidean algorithms.
• An O(M(n) logn) Algorithm for the Jacobi Symbol

This page was built for publication: On the worst case of three algorithms for computing the Jacobi symbol

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q752075)