An O(M(n) logn) Algorithm for the Jacobi Symbol

DOI10.1007/978-3-642-14518-6_10zbMath1260.11081arXiv1004.2091OpenAlexW2104164057MaRDI QIDQ4931642

Paul Zimmermann, Richard P. Brent

Publication date: 29 September 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1004.2091

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16)

Related Items

Improvements on non-interactive zero-knowledge proof systems related to quadratic residuosity languages, Fast computation of the number of solutions to \(x_1^2 + \cdots + x_k^2 \equiv \lambda \pmod{n}\)

Cites Work

• Fast computation of the biquadratic residue symbol.
• Fast computation of continued fraction expansions.
• On Schönhage's algorithm and subquadratic integer gcd computation
• Algorithmic Number Theory
• A note on square roots in finite fields
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item