; Jacobi symbol
; Good
(lambda (a n) (let j ((a a)(n n))
(let ((a (modulo a n))(as arithmetic-shift)) (if (< a 2) a
   (let tw ((a a)) (let ((d (bitwise-and a 15)))
     (if (= 0 d) (tw (as a -4))
     (let ((a (if (odd? d) a (as a
          (vector-ref '#(-4 -1 -2 -1 -3 -1 -2 -1) (as d -1))))))
      (let ((nm (bitwise-and n 7)))
        (* (* (if (even? (as 17732 (- d))) 1 (if (< (abs (- 4 nm)) 2) -1 1))
           (if (and (= (bitwise-and nm 3) 3) (= (bitwise-and a 3) 3)) -1 1))
           (if (= a 1) 1 (j n a))))))))))))
; (as 17732 (- d)) is even iff the number of trailing 0's in d is even.

; slower version using official R5RS arithmetic.
(lambda (a n) (let j ((a a)(n n))
(let ((a (modulo a n))) (if (< a 2) a
   (let tw ((e 0)(a a)) (let ((d (modulo a 8)))
     (if (= 0 d) (tw (+ 3 e)(/ a 8))
     (let ((e (+ e (vector-ref '#(3 0 1 0 2 0 1 0) d)))
           (a (if (odd? d) a (/ a (if (= d 4) 4 2)))))
      (let ((nm (modulo n 8)))
        (* (* (if (even? e) 1 (if (< (abs (- 4 nm)) 2) -1 1))
           (if (and (or (= nm 3) (= nm 7)) (= (modulo a 4) 3)) -1 1))
           (if (= a 1) 1 (j n a))))))))))))

; tests for prime n
(define (t n) (let ((a (make-vector n -1))(J (fileVal "Jacobi")))
  (let r ((k (- n 1))) (if (> k 0)
     (begin (vector-set! a (modulo (* k k) n) 1) (r (- k 1)))))
     (vector-set! a 0 0)
  (let r ((k (- n 1))) (or (< k 0)
    (and (= (vector-ref a k) (J k n)) (r (- k 1)))))))
(t 3) (t 7) ... (t 6700417) (t 100003)

(let ((ng ((((fileVal "RC4") "Seed stuff") 'rbi) 70000)) (J (fileVal "Jacobi")))
(let rt ((n 30000)) (or (zero? n) (and (rt (- n 1))
   (let ((a (+ 3 (* 2 (ng)))) (b (ng)) (c (ng)))
     (= (* (J b a) (J c a)) (J (* b c) a)))))))
