Lower bounds for arithmetic problems

Mansour, Schieber, and Tiwari (1988, 1991) devised a method for obtaining nontrivial lower bounds in models of computations involving the floor operation. Further analysis shows that their techniques can be used to show lower bounds for 3 other types of problems: 1. primality testing, 2. modular exp...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 1991-04, Vol.38 (2), p.83-87
Main Author: MEIDANIS, J
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Computational complexity
Computer science
Computer science
control theory
systems
Exact sciences and technology
Information processing
lower bounds
Mathematical models
primality testing
Theoretical computing
Theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Mansour, Schieber, and Tiwari (1988, 1991) devised a method for obtaining nontrivial lower bounds in models of computations involving the floor operation. Further analysis shows that their techniques can be used to show lower bounds for 3 other types of problems: 1. primality testing, 2. modular exponentiation, and 3. Jacobi symbol. All lower bounds are on the number of operations necessary in the worst case for n-bit integer inputs. The model of computation used is the computation tree, although the bounds also hold for the random access machine (RAM) model. All the constants that appear in the trees that solve the problem for n-bit inputs have to be bounded by some absolute constant. For the RAM model, which is "uniform," this restriction is automatically satisfied since there is only a finite number of constants in a finite program.
ISSN:0020-0190
1872-6119
DOI:10.1016/0020-0190(91)90227-9