A Deterministic Algorithm for Computing Divisors in an Interval

摘要

We revisit the problem of finding a nontrivial divisor of a composite integer when it has a divisor in an interval [α,β]. We use Strassen's algorithm to solve this problem. Compared with Kim-Cheon's algorithms (Math Comp 84(291): 339-354, 2015), our method is a deterministic algorithm but with the same complexity as Kim-Cheon's probabilistic algorithm, and our algorithm does not need to impose that the divisor is prime. In addition, we can further speed up the theoretical complexity of Kim-Cheon's algorithms and our algorithm by a logarithmic term log(β -α) based on the peculiar property of polynomial arithmetic we consider.