3
$\begingroup$

If a prime $p$ can be written as the sum of two squares, then one can construct this representation via Fermat descent if we know an $x$ such that $x^2 \equiv −1 \mod p$. Is there a possibility to say how much steps the Fermat descent will have without just going through the descent?

I have also posted this question on MathStackExchange a week ago (here), but received no answer. I hope it is ok to post it here, too.

EDIT: For example, let $p=1553$. Then $x=339$ and $339^2 + 1^2 = 74 \cdot 1553$. With the descent, we next compute numbers $x_2$, $y_2$ with $x_2^2+y_2^2 = k \cdot 1553$ with $k < 74$. In this case, $x_2=-142$, $y_2=5$ and $x_2^2+y_2^2=13 \cdot 1553$. Going on, in the next step we get $(-9)^2 + (-55)^2 = 2 \cdot 1553$ and finally $(-32)^2 + 23^2 = 1 \cdot 1553$. So here we have three steps: $74 \mapsto 13, 13 \mapsto 2, 2 \mapsto 1$.

Improve this question
$\endgroup$
5
  • $\begingroup$ Can you be a bit more specific? I.e., define what exactly you mean by a "Fermat descent step", if you want exact numbers or bounds, ... Note that the number of steps will usually depend on the square root of $-1$ mod $p$ you start with. $\endgroup$
    – Michael Stoll
    Commented Jan 30, 2015 at 19:07
  • $\begingroup$ @Michael: I made an edit, I hope it is clear now what I mean with "step" $\endgroup$
    – Martin
    Commented Jan 30, 2015 at 19:53
  • $\begingroup$ How did you compute $x_2$? $\endgroup$
    – S. Carnahan ♦
    Commented Jan 30, 2015 at 23:49
  • $\begingroup$ From the example, it appears that the following is used: assume you have $x,y$ with $x^2 + y^2 = kp$. Then take $x' + iy' = (x + iy)(u - iv)/k$ where $u,v$ are the absolutely smallest remainders of $x,y$ mod $k$. In the example, $u = -31$, $v = 1$, which leads to $(x_2, y_2) = (-142, -5)$. $\endgroup$
    – Michael Stoll
    Commented Jan 31, 2015 at 10:52
  • $\begingroup$ Yes, that is the way I computed $x_2,y_2$. $\endgroup$
    – Martin
    Commented Feb 2, 2015 at 12:31

2 Answers 2

Reset to default
3
$\begingroup$

In each iteration of Fermat descent, the multiple of $p$ written as a sum of two squares is at least divided by 2. So if you start with $x>0$ satisfying $x\equiv -1\mod p$, the procedure ends in at most $\log_2(\frac{x^2+1}{p})$ iterations.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Why x/p? x<p, so the log_2() is negative. $\endgroup$
    – joro
    Commented Jan 31, 2015 at 13:04
  • $\begingroup$ Dear joro: Thanks for spotting that. It's now fixed. $\endgroup$
    – P.E.
    Commented Feb 1, 2015 at 0:36
  • $\begingroup$ In the example above this bound would be $6$, whereas the exact number of steps is $3$, so this is a bit too rough. Also, I am more interested in a lower bound. $\endgroup$
    – Martin
    Commented Feb 2, 2015 at 12:36
  • 3
    $\begingroup$ @Martin A well-known an plausible conjecture of Landau (and many others) says that $x^2 + 1$ is a prime number for infinitely many integers $x$. This implies that the lower bound is $0$ steps, since $p = x^2 + 1$ is already a sum of two squares and $x^2 \equiv -1 \bmod p$. $\endgroup$
    – user40023
    Commented Feb 4, 2015 at 10:30
2
$\begingroup$

Let $l$ be the square root of $-1$: $l^2+1\equiv 0 \mod p$. Then from factorization $x^2+y^2\equiv(x+ly)(x-ly)$ we see that a set $$\{(x,y)\in\mathbb{Z}^2:x^2+y^2\equiv 0\mod p\}$$ is the union of two latticies $$\Lambda_\pm=\{(x,y)\in\mathbb{Z}^2:x\pm ly\equiv 0\mod p\}.$$ Each step of Fermat descent is almost the same (but not exactly the same) as a step from Gauss reduction of given basis $(0,p)$, $(\mp l,1)$. It means that it works like "nearest integer continued fraction" algorithm. But vectors $(x_k,y_k)$ may jump between $\Lambda_+$ and $\Lambda_-$, numbers $x_k$, $y_k$ may be reminders or swapped reminders and so on. If you'll need more details on Fermat descent then it will be necessary to take care about all these technical difficulties.

Improve this answer
$\endgroup$

You must log in to answer this question.

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