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 neither 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, for 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.