On the optimality of the binary algorithm for the Jacobi symbol

MaRDI QIDQ3429634zbMATH OpenFDO

Authors

Publication date 2 April 2007

zbMATH Keywords

Jacobi symbollower bounds complexitymodular exponentiationpseudoprimality

Mathematics Subject Classification ID

Power residues, reciprocity (11A15) Primality (11Y11) Number-theoretic algorithms; complexity (11Y16) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Efficient algorithms for computing the Jacobi symbol
• Lower bounds for arithmetic problems
• An O(M(n) logn) Algorithm for the Jacobi Symbol
• scientific article; zbMATH DE number 1113842
• scientific article; zbMATH DE number 919915

Cited in

(7)

• Lower bounds for decision problems in imaginary, norm-Euclidean quadratic integer rings
• Lower bounds for arithmetic problems
• Efficient algorithms for computing the Jacobi symbol
• scientific article; zbMATH DE number 1113842 (Why is no real title available?)
• Computational aspects of rational residuosity
• On the notion of bit complexity
• An O(M(n) logn) Algorithm for the Jacobi Symbol

This page was built for publication: On the optimality of the binary algorithm for the Jacobi symbol

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