; 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)))))))