Efficient algorithms for computing the Jacobi symbol

DOI10.1006/JSCO.1998.0226MaRDI QIDQ1269754zbMATH OpenOpenAlexFDO

Authors Shawna Meyer Eikenberry, Jonathan P. Sorenson

Publication date 23 August 1999

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

Full work available at URL https://doi.org/10.1006/jsco.1998.0226

zbMATH Keywords

Jacobi symbol

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Parallel algorithms in computer science (68W10) Power residues, reciprocity (11A15) Number-theoretic algorithms; complexity (11Y16)

Recommendations

• scientific article; zbMATH DE number 1113842
• An O(M(n) logn) Algorithm for the Jacobi Symbol
• On the optimality of the binary algorithm for the Jacobi symbol
• Computing Jacobi Symbols modulo Sparse Integers and Polynomials and Some Applications

Cited in

(12)

• Efficient algorithms for the gcd and cubic residuosity in the ring of Eisenstein integers
• A randomized sublinear time parallel GCD algorithm for the EREW PRAM
• On the worst case of three algorithms for computing the Jacobi symbol
• Secure sealed-bid online auctions using discreet cryptographic proofs
• On the optimality of the binary algorithm for the Jacobi symbol
• On the Validity of the Φ-Hiding Assumption in Cryptographic Protocols
• scientific article; zbMATH DE number 1113842 (Why is no real title available?)
• An analogue of the Solovay-Strassen test in quadratic Euclidean rings
• An O(M(n) logn) Algorithm for the Jacobi Symbol
• Modular exponentiation via the explicit Chinese remainder theorem
• scientific article; zbMATH DE number 919915 (Why is no real title available?)
• Improvements on non-interactive zero-knowledge proof systems related to quadratic residuosity languages

This page was built for publication: Efficient 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 Q1269754)