home *** CD-ROM | disk | FTP | other *** search
/ Frozen Fish 2: PC / frozenfish_august_1995.bin / bbs / d09xx / d0963.lha / SIOD / scm / prime.scm < prev    next >
Text File  |  1993-05-08  |  1KB  |  46 lines
  1. (define (smallest-divisor n)
  2.         (find-divisor n 2))
  3. (define (find-divisor n test)
  4.         (cond ((> (expt test 2) n) n)
  5.               ((divides? test n) test)
  6.               (else (find-divisor n (add1 test)))))
  7. (define (divides? x y)
  8.         (zero? (remainder y x)))
  9. (define (prime? n)
  10.         (= n (smallest-divisor n)))
  11.  
  12. (define (expmod b e m)
  13.         (cond ((= e 0) 1)
  14.               ((even? e)
  15.                (remainder (expt (expmod b (/ e 2) m) 2) m))
  16.               (else (remainder (* b (expmod b (- e 1) m)) m))))
  17.  
  18. (define (fermat-test n)
  19.         (define a (+ 2 (random (- n 2))))
  20.         (= (expmod a n n) a))
  21.  
  22. (define (carmicael-test n)
  23.         (do ((a 1 (1+ a)))
  24.             ((<> (expmod a n n) a) a)))
  25.  
  26. (define (fast-prime? n times)
  27.         (cond ((= times 0) t)
  28.               ((fermat-test n)
  29.                (fast-prime? n (sub1 times)))
  30.               (else nil)))
  31.  
  32. (define (jacobi a n)
  33.         (cond ((= a 1) 1)
  34.               ((even? a) (* (jacobi (/ a 2) n) (expt -1 (/ (-1+ (expt n 2)) 8))))
  35.               (else (* (jacobi (remainder n a) a) (expt -1 (* (-1+ a) (-1+ n) 1/4))))))
  36.  
  37. (define (solovay-test n)
  38.         (define a (do ((a (+ 2 (random (- n 2))) (+ 2 (random (- n 2)))))
  39.                       ((= (gcd a n) 1) a)))
  40.         (= (expmod a (/ (-1+ n) 2) n) (jacobi a n)))
  41.  
  42. (define (fast-prime-sol? n times)
  43.         (do ((tim times (-1+ tim))
  44.              (good 0 (if (solovay-test n) (1+ good) good)))
  45.             ((= tim 0) (< good (/ n 2)))))
  46.