2
$\begingroup$

Let a gaussian circle $C_R$ be any circle defined by the equation:

$$x^2+y^2 = R, (x,y) \in \mathbb{R}^2$$, where $R$ is the norm of a gaussian integer ($R=a^2+b^2, (a,b) \in \mathbb{Z}^2$). IF $R$ contains $n$ prime factors, it is not hard to show that $C_R$ contains $2^{n+2}$ integer points organized in $2^n$ classes of 4 elements. For example, with $R=65=5\times 13$ we have the only 4 integer points classes: $(\pm4,\pm7), (\pm8, \pm1), (\pm7,\pm4)$ and $(\pm1, \pm8)$.

We define the "non-abelian" addition law $\times$ on $C_R$ as follows:

$$(x_0, y_0) \times (x_1, y_1) = \frac{1}{R}\left(x_0\left(x_1^2-y_1^2\right)-2y_0x_1y_1, 2x_0x_1y_1+y_0 \left(x_1^2-y_1^2\right)\right),$$

the set of all rational points on $C_R$ forms a semigroup $G_R$, and if $P$ is an integer point on $C_R$ the set generated by repeated addition is dense on $C_R$.

Suppose now that $R$ factorization is unknown. Is it possible to find any non-trivial rational point on $C_R$?

I suspect the answer is no, otherwise we could easily factor large Gaussian integers. On the other hand, since rational points are dense on $C_R$, we have an infinity to choose from ...

$\endgroup$
3
  • $\begingroup$ Thanks for your answers, already a great advancement on my side. This makes me realize how poorly stated the original question was. I am currently working on a clean and precise formulation for another post. $\endgroup$
    – Aobara
    Sep 12, 2012 at 13:39
  • $\begingroup$ Your "non-abelian group law" is not associative, nor does it have a neutral element. Therefore you should probably not talk about the subgroup generated by P. $\endgroup$ Sep 13, 2012 at 12:44
  • $\begingroup$ Thanks for pointing that out. I did not realize the neutral element was missing... $\endgroup$
    – Aobara
    Sep 13, 2012 at 17:12

3 Answers 3

3
$\begingroup$

Answering mainly about "any nontrivial rational point".

Don't think factoring becomes easy even if an oracle gave you one integral point.

For some numbers such oracle come for free, e.g. for $R=u^2+1$ the point is $(u,1)$. Fermat numbers are of such form and they are hard to factor.

Since your problem is a genus 0 curve over $\mathbb{Q}(i)$ you can parametrize all rational points:

$$ x,y=(- i R+ i t^2)/(2t),(R+t^2)/(2 t)$$

$\endgroup$
11
  • $\begingroup$ IF there are $N$ integral points P1,...,PN on CR, rational points can be organized into N separate classes: $$U_R=\left \{ u = \frac{x+iy}{z} | (x,y,z)\in \mathbb{Z}^3, z^2=x^2+y^2, GCD(z,R)=1 \right \}$$ $$R_i = \left\{ P_i . u | u \in U_R \right\}, i=1...N $$ Indeed, for factorization, two rational points are at least needed and they have to belong to distinct classes. – $\endgroup$
    – Aobara
    Sep 12, 2012 at 9:42
  • $\begingroup$ Note that I am really considering the case $x,y \in \mathbb{Q}^2$, which is harder than looking for solutions over $\mathbb{Q}(i)$ $\endgroup$
    – Aobara
    Sep 12, 2012 at 11:00
  • 1
    $\begingroup$ @handelskai if you are interested only in Q, R=u^2+1 gives you infinitely many points - multiply $u+i$ by something of norm $1$. Solving over Q will give an algorithm for expressing R as a sum of two squares :-) $\endgroup$
    – joro
    Sep 12, 2012 at 11:22
  • $\begingroup$ I have to accept this answer I am afraid, even though I am still a bit disappointed ;) This indeed gives an algorithm for generating infinitely many rational points, unfortunately, the required initial form $R=u^2+1$ forces the generated points to remain within the same Class $P_1$. This bolds down to the fact that factorization is equivalent to knowing 2 strictly (not trivially related) distinct different integer points. $\endgroup$
    – Aobara
    Sep 12, 2012 at 11:34
  • 1
    $\begingroup$ Numeric example: Take R=221=5^2+14^2=10^2+11^2. Suppose you know (5,14). This gives the parametrization over Q: (x,y)=(5*T^2 - 28*T - 5)/(T^2 + 1),(14*T^2 + 10*T - 14)/(T^2 + 1). T= -5 gives the point (10,11) which is the other solution. Finding T is hard. $\endgroup$
    – joro
    Sep 12, 2012 at 12:40
8
$\begingroup$

Well, there are some easy points on $C_R$. The point $((1+R)/2, (1-R)/(2i))$, for example.

More generally, the equation $x^2+y^2=R$ is equivalent to $(x+iy)(x-iy) = R$. So finding a rational point on $C_R$ is exactly equivalent to finding $u$ and $v$ in $\mathbb{Q}(i)$ with $uv=R$. You can do that by choosing $u$ at random, and computing $v=R/u$, $x=(u+v)/2$ and $y=(u-v)/(2i)$. I took $u=1$ above.

But, as you say, if we had any way to find nontrivial solutions with $u$ and $v$ Gaussian integers, then we would have a way to factor Gaussian integers, and that is believed to be difficult.

$\endgroup$
5
  • $\begingroup$ Are you aware of any literature on the difficulty of factoring Gaussian integer? Would be very helpful. Thanks $\endgroup$
    – Aobara
    Sep 11, 2012 at 18:34
  • 1
    $\begingroup$ Well, if you can factor Gaussian integers, you can factor integers. Conversely, if you can factor integers, you can factor Gaussian integers: See stackoverflow.com/a/2271645 . I assume you understand that factorization is expected not to be in P (although there is no proof) although perhaps to be easier that NP-complete? $\endgroup$ Sep 11, 2012 at 20:43
  • $\begingroup$ I understand that factoring gaussian integers partially solves the more general problem of factoring arbitrary integers, simply because gaussian integers are a subset of integers. However, if you can factor gaussian integers there is no warranty that you can factor arbitrary integers. Additionally, I am aware of the fact that there are trivial solutions to this problem, and ,really, especially due to their trivial nature, I have very little interest in them. Thanks, however, for attempting to provide an answer. $\endgroup$
    – Aobara
    Sep 11, 2012 at 21:47
  • $\begingroup$ "gaussian integers are a subset of integers." Really? Thought it was the other way around. What definitions are you using? $\endgroup$ Sep 11, 2012 at 22:32
  • 1
    $\begingroup$ I should have said "norm of a gaussian integer", sorry. I am looking at $R$ in the form $a^2+b^2$, my bad... $\endgroup$
    – Aobara
    Sep 12, 2012 at 8:03
4
$\begingroup$

Perhaps the situation becomes clearer by looking at a similar problem. Replacing the circle by a hyperbola, we can look at rational points on $H: XY = R$. This conic has the obvious point $N = (1,R)$, and among the many rational points on $H$ there are a few integral points, each corresponding to a factorization of $R$. You can define a group law on $H$ with neutral element, but this does not help at all at finding "nontrivial" rational points (that is, integral points). Neither does it seem to help to replace the rationals by an algebraic number field. In fact the geometric picture does not seem to add to our understanding in this case (on this elementary level, at least).

$\endgroup$
1
  • $\begingroup$ Many thanks for this explanation. It does set things in perspective ;) $\endgroup$
    – Aobara
    Sep 14, 2012 at 12:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.