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

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

Review text

The author considers the worst case computation of the Jacobi symbol \((\frac{u}{v})\) by analogues of the Euclidean algorithm. One can insist on even quotients (Eisenstein), least remainders (Lebesgue), or the ordinary algorithm, (reducing even factors as they occur). For the first type the worst case is \(u=2n+1\), \(v=2n-1\), for the second and third types of the worst cases generate fascinating quadratic and sextic recurrences. The logarithmic character of the algorithm is easily upheld.

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

• 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.
• 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?)
• On a theorem of Heilbronn
• Prime numbers and computer methods for factorization
• The Jacobi symbol algorithm
• Über die mittlere Schrittanzahl bei Divisionsalgorithmen
• Über die Schrittanzahl beim Algorithmus von Harris und dem nach nächsten Ganzen

Cited in

(5)

• Dynamical analysis of a class of Euclidean algorithms.
• Comments on search procedures for primitive roots
• scientific article; zbMATH DE number 1113842 (Why is no real title available?)
• Computations of class numbers of real quadratic fields
• 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)