Computing prime divisors in an interval
Minkyu Kim, Jung Hee Cheon · Mathematics of Computation · 2014
We address the problem of finding a nontrivial divisor of a composite integer when it has a prime divisor in an interval. We show that this problem can be solved in time of the square root of the interval length with a similar amount of storage, by presenting two algorithms; one is probabilistic and the other is its derandomized version.