OFFSET
1,1
COMMENTS
Representing a given prime P=3k+1 as x^2+3y^2 amounts to finding the shortest vector in a 2-dimensional lattice, namely either of the primes above P in the ring Q(sqrt(-3)). For instance, if P = 2^521 - 1 then P = x^2 + 3y^2 where x,y are 2107597973657165184339850860393713575649657317180489057212823189967494080057958, 898670952308059000662208200339860406351380028634597445743368513219427297854627. - Noam D. Elkies, Jun 25 2001
REFERENCES
F. Lemmermeyer, Reciprocity Laws From Euler to Eisenstein, Springer-Verlag, 2000, p. 59.
LINKS
Phil Moore, Tony Reix and others, Online Discussion
EXAMPLE
p=7: 127 = 10^2 + 3*3^2, so a(3) = 10.
PROG
(PARI) f(p, P, a, m)= P=2^p-1; a=lift(sqrt(Mod(-3, P))); m=[P, a; 0, 1]; (m*qflll(m, 1))~[1, ]
for(n=1, 11, print(abs(f([3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 521][n])[1]))) \\ Joshua Zucker, May 23 2006
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
N. J. A. Sloane, Feb 05 2001
EXTENSIONS
More terms from Noam D. Elkies, Jun 25 2001
Corrected and extended by Joshua Zucker, May 23 2006
STATUS
approved