Speeding the quadratic sieve with an oracle

Question

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?)

1. 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?

2. 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.

Answer 1

If we know the factorization of $N$ then we can take square roots of small numbers that are quadratic residues mod all primes dividing $N$. Knowing a partial factorization of size $M\sim N^\alpha$, square a number close to $N^{1/2−\alpha/2}$ mod $N/M$, find a root mod $M$, then use crt to find the root mod $N$. We have a found a square that is of size $N^{1/2−\alpha/2}$ instead of $N^{1/2}$.