Bisection method is a method used to find solutions to an expression of some sort, usually an equation.  It's very simple to use.  If you know a solution lay within an interval, divide the interval into two and decide which subinterval then has the solution and then repeat the process using that subinterval.
Surprisingly it is very efficient and the number of iterations necessary to iterate until precision is met is given by
n > (ln(b-a)-ln(E))/ln(2) on the interval [a,b] with error E

So, you might wonder how might this be used to factor a number quickly.  Yoni noted to me the other day that deterministic composite factorization has been proven to be a non polynomial time problem.  However we might be able to use statistics and probability to do this and ensure that it works most of the time.
Consider a number p = ab for positive integers a and b and assume b >= a.
then we can see that b >= sqrt(p) >= a
The potentially smallest factor is 2 since we can ignore 1.  We now know an interval [2, sqrt(p)] on which the factor may exist.  We can use the bisection method and divide that interval into two and decide which subinterval to choose and repeat the process.  The problem would be choosing the subinterval and doing this deterministically could potentially be very slow, but it might be possible to use probability to determine the odds an integer factor may or may not lie on that interval.  Of course, we'd have to compare it to the probability on the other subinterval to choose the more likely subinterval.  This probability may not be as tedious to calculate as, say, checking each integer for divisibility.  Since it is indeed probability, it can potentially fail for some numbers.

So, you might wonder how many iterations it may take for tolerable precision.
If we consider a million digit number 10^(10^6), we are working with the interval [2, 10^500000].  Then we can estimate the necessary iterations with the above expression n > (ln(10^500000-2)-ln(E))/ln(2)
Let's assume E is tolerable when .01 < E < .001.  Since 10^500000 is so large we can safely assume that 2 and ln(E) will not majorly effect the overall estimate.
We then are left with
n > ln(10^500000)/ln(2) = 500000*ln(10)/ln(2) ~ 1.66 million iterations which is pretty good if I might say so.

Supposedly there are statistical distributions of the primes, this could potentially be very helpful.

To summarize, does someone know a good algorithm that answers this question:

"Does the number n have an integer factor in the interval [a, b]?"

It has to be deterministic, polynomial time-complexity, and correct at a probability of 50% or more (not necessarily 100%).

[quote author=Yoni link=topic=11480.msg111048#msg111048 date=1115230126]
To summarize, does someone know a good algorithm that answers this question:

"Does the number n have an integer factor in the interval [a, b]?"

It has to be deterministic, polynomial time-complexity, and correct at a probability of 50% or more (not necessarily 100%).
[/quote]

Not necessarily.  If we know that the number is composite and a factor exists on [a,b], then if we compare the probabilities of [a,(a+b)/2] and [(a+b)/2,b] and choose the larger probability, this could potentially be deterministic regardless of how small the probabilities are, but iif we know the number is composite.