A problem concerning a character sum

Let p be a prime congruent to -1 module 4, (n/p) the Legendre symbol and S( k) = Sigma(n=1)(p-1) n(k)(n/p). The problem of finding a prime p such that S(3) > 0 was one of the motivating forces behind the development of several of Shanks' ideas for computing in algebraic number fields, although neithe r he nor D.H. and Emma Lehmer were ever successful in finding such a p. In this paper we exhibit some techniques which were successful in producing, f or each k such that 3 less than or equal to k less than or equal to 2000, a value for p such that S(k) > 0.