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

  • $\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$ – handelskai Sep 12 '12 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$ – Franz Lemmermeyer Sep 13 '12 at 12:44
  • $\begingroup$ Thanks for pointing that out. I did not realize the neutral element was missing... $\endgroup$ – handelskai Sep 13 '12 at 17:12

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

  • $\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$ – handelskai Sep 12 '12 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$ – handelskai Sep 12 '12 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 '12 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$ – handelskai Sep 12 '12 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 '12 at 12:40

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.

  • $\begingroup$ Are you aware of any literature on the difficulty of factoring Gaussian integer? Would be very helpful. Thanks $\endgroup$ – handelskai Sep 11 '12 at 18:34
  • $\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$ – David E Speyer Sep 11 '12 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$ – handelskai Sep 11 '12 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$ – Gerry Myerson Sep 11 '12 at 22:32
  • $\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$ – handelskai Sep 12 '12 at 8:03

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

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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