Suppose we have an odd composite $N$ and want to find numbers $a_1,\ldots,a_k$ such that each $a_i^2$, reduced mod $N$, is $b$-smooth. Of course we can use the quadratic sieve algorithm (minus the matrix step) to find such $a_i$. With a factorization oracle, they could be found directly by factoring small squares—the quadratic sieve without the "sieve" part. (I assume there's no faster way in this case than generating [presumably sequentially, to avoid actual divisions] and testing?)

If instead of a general factoring oracle we had access to an oracle for the factors of N, could we improve on the speed of the quadratic sieve?

Harder: If we had only a partial factorization of $N$ (say, of size $N^{2/5}$), could we improve on the speed?

Algorithms, heuristics, and reductions to known hard problems would be welcome. You may assume that $k$ and $b$ are reasonable: there are $\gg k$ solutions.