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.

Advertisements

Pages: 1 2

One Response to “Gauss’s Criterion”

  1. Daniel said

    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)
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: