Bleichenbacher 1998 "Million message attack" on RSA
I implemented this padding oracle attack some time ago in Python and remember this part being a bit confusing to wrap my head around, my code is as follows:

newM = []
for (a, b) in M:
    # util.ceiling rounds arg1 / arg2 to the next highest integer
    rlow = util.ceiling((a*s - 3*B + 1), n)
    rhigh = (b*s - 2*B) / n

    for r in range(rlow, rhigh + 1):
        newa = max(a, util.ceiling(2*B + r*n, s))
        newb = min(b, (3*B - 1 + r*n) / s)
        newM.append((newa, newb))

M = list(set(newM))


So basically for each (a, b) pair in the set M you have to calculate the range of possible r values and create a new pair for each r. Since the pairs (a, b) are such that a &lt;= b, calling max for the first element and min for the second element ensures that for any (a, b) the new value of a can only increase and b can only decrease. Said another way, you never increase the range, you are always narrowing it down. So while the amount of pairs in M does increase for a while it eventually does decrease back down to one pair (a, b) where a = b.

Hope that is somewhat helpful. :)