7
$\begingroup$

Fermat famously showed that the only primes $p$ of the form $x^2 + y^2$ are the primes such that $p \equiv 1 \mod{4}$. Furthermore, we now know “effective” versions of Fermat's theorem, i.e. given a prime $p$ such that $p \equiv 1 \mod{4}$, we know how to find integers $x$, $y$ such that $x^2 + y^2 = p$ in time polynomial in $\log p$ (see, for example section 4.5 in [1]). I would like an analogous theory for primes of the form $x^2 + xy + y^2$. In other words, I would like a precise characterization of which primes $p$ can be expressed in this form (EDIT: The comments explain that these are the primes $\not\equiv 2\mod 3$), as well as an efficient algorithm to obtain such a factorization given $p$.

  1. Shoup, Victor, A computational introduction to number theory and algebra, Cambridge: Cambridge University Press (ISBN 978-0-521-51644-0/hbk). xvii, 580 p. (2009). ZBL1196.11002.
Improve this question
$\endgroup$
16
  • 11
    $\begingroup$ These are well known to be the prime rational integers which do not remain prime in the ring of Eisenstein integers $\mathbb{Z}[\omega]$, where $\omega$ is a primitive complex cube root of unity. These are the rational primes congruent to $1$ (mod $3$), and the rational prime $3$. $\endgroup$
    – Geoff Robinson
    Commented Sep 13, 2020 at 21:39
  • 10
    $\begingroup$ gp-pari code: $$ $$ eisen(p,v) = v=abs(qflll([lift((sqrt(Mod(-3,p))+1)/2),p;1,0])[1,]); if(v*v~>p, [vecmin(v),abs(v[1]-v[2])], v) $$ $$ For example, eisen(100000000003) returns [103166, 251761]. $\endgroup$
    – Noam D. Elkies
    Commented Sep 13, 2020 at 22:11
  • 6
    $\begingroup$ (There’s also a “formula” for such $x$ and $y$, namely $x - y \zeta_3 = J(\chi, \chi) = \sum_{a\in \mathbb{F}_p} \chi(a) \chi(1-a)$, where $\chi: \mathbb{F}_p^\times\to \{1, \zeta_3, \zeta_3^2\}$ is a cubic character mod $p$.) $\endgroup$
    – alpoge
    Commented Sep 13, 2020 at 22:20
  • 15
    $\begingroup$ @YCor Actually you can! You just need a cube root of unity mod $p$, which is easy in random polynomial time, and even possible deterministically thanks to Schoof's algorithm (which is related with alpoge's comment). Then Euclid or 2-dimensional LLL is polynomial time. For example, the smallest 500 digit prime is $10^{499} + 153$, which happens to be 1 mod 3, and "eisen" takes only 12 milliseconds to find its $(x,y)$. $\endgroup$
    – Noam D. Elkies
    Commented Sep 13, 2020 at 22:32
  • 6
    $\begingroup$ [2463505687802154058859226730108383571591600256629173176364980024555626670349497123082936620270065106374169122856933117712904951390428449265056103980972775860781270581881580532542195873409432401268688833706520165493628574413068924000927599285073761949, 1102418271211271989374012922279714325115202464904081123218798301995385992754729584967829222778046361602101500269511074106202422438370926118997383768231376869226103315918023605989878251994931215507091583589312445322666942269948872277385599352796657552] $\endgroup$
    – Noam D. Elkies
    Commented Sep 13, 2020 at 22:32

1 Answer 1

Reset to default
15
$\begingroup$

This is an elaboration of the answer that Noam Elkies provided in the comments.

Suppose that $p=x^2 + xy + y^2$. Then note that $x$ and $y$ are small relative to $p$ (at most half as many digits). Note also that if $\zeta \not\equiv 1\pmod p$ satisfies $\zeta^3 \equiv 1\pmod p$ then $\zeta^2 + \zeta + 1 \equiv 0 \pmod p$, so $$(x - \zeta y)(x - \zeta^2 y) = x^2 - (\zeta+\zeta^2)xy + \zeta^3 y^2 \equiv x^2 + xy + y^2 \equiv p \equiv 0 \pmod p.$$ Therefore either $x \equiv \zeta y \pmod p$ or $x \equiv \zeta^2 y \pmod p$; in the latter case we have $\zeta x \equiv y \pmod p$. This means that in the 2-dimensional integer lattice generated by the vectors $(1,\zeta)$ and $(0,p)$, there is an unusually short vector $(y,x)$ or $(x,y)$, which can be found by lattice-basis reduction as long as we have $\zeta$.

It remains to find $\zeta$. Formally, we can write $$\zeta := {\sqrt{-3} - 1 \over 2},$$ and it is easy to check that if we can find a square root of $-3$ modulo $p$ then this formula does indeed give us a cube root of unity modulo $p$. But computing the square root can be done using the Tonelli–Shanks algorithm or Schoof's algorithm.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I should remark that $x$ could be slightly larger than $\sqrt p$ if $y$ is negative. But if $p = x^2 - xy + y^2 = (x-y)^2 + xy$ for some $x>0$ and $y>0$ then $|x-y| < \sqrt p$. So neither $x$ nor $y$ can be much larger than $\sqrt p$, because then $xy$ would be larger than $p$. $\endgroup$
    – Timothy Chow
    Commented Sep 19, 2020 at 21:01

You must log in to answer this question.

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