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.



Speeding the quadratic sieve with an oracle
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}$.


