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.


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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.