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 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 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>