On the optimality of the binary algorithm for the Jacobi symbol

zbMATH Open1111.11061MaRDI QIDQ3429634FDOQ3429634

Authors:

Publication date: 2 April 2007

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

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)

Cited In (5)

• Lower bounds for decision problems in imaginary, norm-Euclidean quadratic integer rings
• On the notion of bit complexity
• Title not available (Why is that?)
• 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)