Would an oracle for integral points on elliptic curves be a factoring oracle? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T23:56:41Z http://mathoverflow.net/feeds/question/50794 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/50794/would-an-oracle-for-integral-points-on-elliptic-curves-be-a-factoring-oracle Would an oracle for integral points on elliptic curves be a factoring oracle? jerr18 2010-12-31T07:59:24Z 2010-12-31T10:10:04Z <p>Oracle finding all integral points on genus 0 curves is a factoring oracle (e.g. \$xy=n\$ and \$x^2-y^2=n\$</p> <p>I asked <a href="http://mathoverflow.net/questions/50479/can-the-number-of-solutions-xyx-y-1n-for-x-y-n-in-z-be-unbounded-as-n-var" rel="nofollow">Can the number of solutions \$xy(x−y−1)=n\$ for x,y,n∈Z be unbounded as n varies?</a> and occurred to me that an oracle giving all integral points may find nontrivial factor of \$n\$. Drama is this will not work for all \$n\$.</p> <p>Would an oracle for finding all integral points on genus 1 curves (in whatever model) be:</p> <ol> <li>(loosely defined) Weak factoring oracle which finds at least one nontrivial factor</li> <li>Strong factoring oracle which finds all prime factors?</li> </ol> <p>The factoring oracle must work for all integers if it exists.</p> <p>(EDIT): Intuitively if I had genus 0 oracle for integral points I could factor general integers. If the oracle were for genus 1 I don't see a way for general integers but I would be lucky with integers of the form \$xy(x-y-1)\$ (just an example)</p> http://mathoverflow.net/questions/50794/would-an-oracle-for-integral-points-on-elliptic-curves-be-a-factoring-oracle/50797#50797 Answer by Franz Lemmermeyer for Would an oracle for integral points on elliptic curves be a factoring oracle? Franz Lemmermeyer 2010-12-31T10:10:04Z 2010-12-31T10:10:04Z <p>An integral point (actually, a rational point in the affine plane will do) on an elliptic curve \$y^2 = x(x^2 + ax + b)\$ comes (by the standard technique of simple 2-descent) from a rational point on some quartic \$\$ N^2 = b_1M^4 + aM^2e^2 + b_2e^4, \$\$ where \$b_1b_2 = b\$. Thus if you want to factor an integer \$N\$, ask the oracle for (rational) points on the curve \$y^2 = x(x^2 + ax + N)\$ for sufficiently many values of \$a\$ until you find a point that gives you a nontrivial factorization \$N = b_1b_2\$. If you choose \$a\$ in such a way that the parity conjecture predicts an odd rank, you will know in advance that such a point exists. </p> <p>A similar technique works for the Pell equation and shows that solving the Pell equation \$T^2 - dU^2 = 1\$ is at least as hard as factoring \$d\$.</p>