Gauss’s Criterion
May 1, 2018
This isn’t hard, though I admit I mixed up b and p the first time I did it:
(define (gauss-criterion b p) (define (gauss 2k-1) (modulo (* 2k-1 b) p)) (expt -1 (length (filter even? (filter positive? (map gauss (range 1 p 2)))))))
And here is a demonstration that it correctly computes the Legendre symbol:
> (do ((ps (cdr (primes 100)) (cdr ps))) ((null? ps))
(do ((b 1 (+ b 1))) ((= (car ps) b))
(assert (gauss-criterion b (car ps))
(jacobi b (car ps)))))
No news is good news. You can run the program at https://ideone.com/ONFr06.
Programming Praxis 
Here’s a solution in Python 2.
def legendre(b, p): l = (b ** ((p - 1) / 2)) % p if l == p - 1: l = -1 return l def gauss(b, p): r = ((x * b) % p for x in xrange(1, p, 2)) t = sum(1 for x in r if (x % 2) == 0) return (-1) ** t ps = [3, 5, 7, 11, 13, 17, 19, 23, 29] for p in ps: for b in range(1, p): assert gauss(b, p) == legendre(b, p)