most recent 30 from http://mathoverflow.net 2013-06-19T07:17:03Z http://mathoverflow.net/feeds/question/39567 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/39567/speeding-the-quadratic-sieve-with-an-oracle Charles 2010-09-22T01:11:48Z 2010-10-02T22:46:25Z

<p>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&mdash;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?)</p> <ol> <li><p>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?</p></li> <li><p>Harder: If we had only a partial factorization of $N$ (say, of size $N^{2/5}$), could we improve on the speed?</p></li> </ol> <p>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.</p>

http://mathoverflow.net/questions/39567/speeding-the-quadratic-sieve-with-an-oracle/40881#40881 Dror Speiser 2010-10-02T22:46:25Z 2010-10-02T22:46:25Z

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