Efficient algorithms for computing the Jacobi symbol

DOI10.1006/JSCO.1998.0226zbMATH Open0919.68075OpenAlexW2062262765MaRDI QIDQ1269754FDOQ1269754

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

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

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)

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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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)