Computing Jacobi Symbols modulo Sparse Integers and Polynomials and Some Applications

DOI10.1006/JAGM.2000.1091MaRDI QIDQ4500854zbMATH OpenOpenAlexFDO

Authors Igor E. Shparlinski

Publication date 22 November 2000

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.2000.1091

zbMATH Keywords

Jacobi symbols of exponentially large integerspolynomial time algorithmpseudorandom bitssparse integerssparse polynomialsstream ciphers

Mathematics Subject Classification ID

Power residues, reciprocity (11A15) Polynomials over finite fields (11T06) Number-theoretic algorithms; complexity (11Y16)

Recommendations

• Efficient algorithms for computing the Jacobi symbol
• Efficient algorithms for computing the Jacobi symbol. (Extended abstract)

Cited in

(7)

• Efficient algorithms for computing the Jacobi symbol
• An algorithm for numerically inverting the modular \(j\)-function
• Efficient algorithms for computing the Jacobi symbol. (Extended abstract)
• Computational aspects of rational residuosity
• An O(M(n) logn) Algorithm for the Jacobi Symbol
• Detecting lacunary perfect powers and computing their roots
• The one-wayness of Jacobi signatures

This page was built for publication: Computing Jacobi Symbols modulo Sparse Integers and Polynomials and Some Applications

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