6
$\begingroup$

Oracle finding all integral points on genus 0 curves is a factoring oracle (e.g. $xy=n$ and $x^2-y^2=n$

I asked Can the number of solutions $xy(x−y−1)=n$ for x,y,n∈Z be unbounded as n varies? 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$.

Would an oracle for finding all integral points on genus 1 curves (in whatever model) be:

  1. (loosely defined) Weak factoring oracle which finds at least one nontrivial factor
  2. Strong factoring oracle which finds all prime factors?

The factoring oracle must work for all integers if it exists.

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

Improve this question
$\endgroup$
2
  • $\begingroup$ So, to be clear, the oracle would detect if the curve was genus 1 and not return an answer if it wasn't? $\endgroup$
    – Qiaochu Yuan
    Commented Dec 31, 2010 at 8:20
  • $\begingroup$ @Qiaochu OK. Yes, the oracle will not return an answer if the curve is not genus 1. $\endgroup$
    – jerr18
    Commented Dec 31, 2010 at 9:20

1 Answer 1

Reset to default
8
$\begingroup$

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.

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you. How do you define "sufficiently many values of $a$" ? $\endgroup$
    – jerr18
    Commented Dec 31, 2010 at 10:58
  • $\begingroup$ It means "until you find a factor". Points on $E \setminus 2E$ usually come from a nontrivial factorization, but there's no guarantee. The same thing holds in the Pell case; if nothing works, you can always replace $N$ by $kN$ for some small value of $k$ and find a factorization of $kN$. $\endgroup$
    – Franz Lemmermeyer
    Commented Dec 31, 2010 at 17:10
  • $\begingroup$ @Franz solving the Pell equation $x^2−dy^2=1$ is tractable for d a Fermat number (and possibly for $d=a^2+1$). Experimentally the period of the continued fraction of sqrt(d) is very small. Would that help factoring by any chance? $\endgroup$
    – joro
    Commented Jul 21, 2011 at 11:51
  • $\begingroup$ Yes, if $d=a^2+1$ then the continued fraction is $[a,2a,2a,2a,2a,2a,\ldots]$ and the fundamental solution of $x^2-dy^2=+1$ is $(2a^2+1,2a)$. $\endgroup$
    – Noam D. Elkies
    Commented Mar 7, 2012 at 22:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .