On the optimality of the binary algorithm for the Jacobi symbol

MaRDI QIDQ3429634zbMATH OpenFDO

Authors

Publication date 2 April 2007

zbMATH Keywords

Jacobi symbolmodular exponentiationpseudoprimalitylower bounds complexity

Mathematics Subject Classification ID

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

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

(5)

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

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)