Lower bounds for arithmetic problems

DOI10.1016/0020-0190(91)90227-9MaRDI QIDQ1178201zbMATH OpenOpenAlexWikidataFDO

Authors João Meidanis

Publication date 26 June 1992

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://digital.library.wisc.edu/1793/59386

zbMATH Keywords

Jacobi symbollower boundsmodular exponentiationprimality testing

Mathematics Subject Classification ID

Primality (11Y11) Number-theoretic algorithms; complexity (11Y16) Analytic computations (11Y35) Analysis of algorithms and problem complexity (68Q25)

Review text

The author shows that the method developed by \textit{Y. Mansour}, \textit{B. Schieber}, and \textit{P. Tiwari} [SIAM J. Comput. 20, No.\ 2, 315-327 (1991; Zbl 0724.68051)] can be used to obtain the lower bounds for the following arithmetic problems: primality testing, modular exponentiation, Jacobi symbol.

Recommendations

• On the optimality of the binary algorithm for the Jacobi symbol
• Arithmetic complexity
• A lower bound for primality
• Lower bounds on arithmetic circuits via partial derivatives
• Circuit and decision tree complexity of some number theoretic problems

Cites work

• Approximate formulas for some functions of prime numbers
• scientific article; zbMATH DE number 3657869 (Why is no real title available?)
• scientific article; zbMATH DE number 3757704 (Why is no real title available?)
• scientific article; zbMATH DE number 47996 (Why is no real title available?)
• scientific article; zbMATH DE number 4117838 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• scientific article; zbMATH DE number 3105562 (Why is no real title available?)
• On Linnik's constant

Cited in

(10)

• Lower bounds for decision problems in imaginary, norm-Euclidean quadratic integer rings
• Lower bound arguments with ``inaccessible numbers
• A lower bound for range enclosure in interval arithmetic
• scientific article; zbMATH DE number 5862941 (Why is no real title available?)
• On the optimality of the binary algorithm for the Jacobi symbol
• Arithmetic complexity
• Lower Bounds for Geometrical and Physical Problems
• A lower bound for primality
• On defining integers and proving arithmetic circuit lower bounds
• Correlation and lower bounds of arithmetic expressions

This page was built for publication: Lower bounds for arithmetic problems

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