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

DOI10.1016/S0747-7171(08)80160-5zbMath0715.11072OpenAlexW1967135503MaRDI QIDQ752075

Jeffrey O. 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) Number-theoretic algorithms; complexity (11Y16) Power residues, reciprocity (11A15)

Related Items (3)

Dynamical analysis of a class of Euclidean algorithms. ⋮ Comments on search procedures for primitive roots ⋮ Computations of class numbers of real quadratic fields

Cites Work

• Über die Schrittanzahl beim Algorithmus von Harris und dem nach nächsten Ganzen
• Computational problems associated with Racah algebra
• Fast computation of continued fraction expansions.
• A modification of the RSA public-key encryption procedure (Corresp.)
• The Jacobi symbol algorithm
• On a theorem of Heilbronn
• Erratum: A Fast Monte-Carlo Test for Primality
• Über die mittlere Schrittanzahl bei Divisionsalgorithmen
• Prime numbers and computer methods for factorization
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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