MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 1 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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