The iterated mod problem

The iterated mod problem is this: given a, b 1, b 2, …, b n, all integers or all polynomials in Q [x], is ((… ((a mod b 1) mod b 2) …) mod b n ) = 0? When the inputs are integers, we prove the problem P-complete with respect to log-space reductions, whereas in the polynomial case, we prove the problem is in NC. The significance of these results lies primarily in the similarity between the iterated mod problem and the Euclidean algorithm. We also show that the superincreasing knapsack problem is P-complete, using a very similar proof.

Authors

• Howard J. Karloff
• Walter L. Ruzzo

Keywords

No keywords are indexed for this paper.