Lower bounds for arithmetic problems

DOI10.1016/0020-0190(91)90227-9zbMath0748.11061OpenAlexW2163019574WikidataQ127358838 ScholiaQ127358838MaRDI QIDQ1178201

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

modular exponentiationlower boundsJacobi symbolprimality testing

Mathematics Subject Classification ID

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

Related Items

A lower bound for primality ⋮ Lower bounds for decision problems in imaginary, norm-Euclidean quadratic integer rings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximate formulas for some functions of prime numbers
• On Linnik's constant