Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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)

share|improve this question
    
So, to be clear, the oracle would detect if the curve was genus 1 and not return an answer if it wasn't? –  Qiaochu Yuan Dec 31 '10 at 8:20
    
@Qiaochu OK. Yes, the oracle will not return an answer if the curve is not genus 1. –  jerr18 Dec 31 '10 at 9:20
add comment

1 Answer

up vote 8 down vote accepted

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

share|improve this answer
    
Thank you. How do you define "sufficiently many values of $a$" ? –  jerr18 Dec 31 '10 at 10:58
    
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$. –  Franz Lemmermeyer Dec 31 '10 at 17:10
    
@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? –  joro Jul 21 '11 at 11:51
    
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)$. –  Noam D. Elkies Mar 7 '12 at 22:37
add comment

Your Answer

 
discard

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.