米勒-拉宾素性检验

miller-rabin.scm

#lang scheme
(define (square x) (* x x))

(define (gcd a b)
  (if (= 0 b)
      a
      (gcd b (remainder a b))))

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

(define (fast-expt-iter result x y)
  (cond ((= y 0) result)
        ((even? y) (fast-expt-iter result (* x x) (/ y 2)))
        (else (fast-expt-iter (* result x) x (- y 1)))))

(define (fast-expt x y) (fast-expt-iter 1 x y))

(define (div2 n)
  (div-iter 2 n 0))

(define (div-iter mod d s)
  (if (= 0 (remainder d mod))
       (div-iter mod (floor (/ d mod)) (+ s 1))
       (list s d)))

(define (miller-rabin-test n)
  (define (try-it a r d)
      (or
       (= 1 (expmod a d n))
       (= (- n 1) (expmod a (* (fast-expt 2 r) d) n))))

  (define (try-iter a now r d)
    (cond ((> now r) false)
          ((try-it a now d) true)
          (else (try-iter a (add1 now) r d))))

  (let ((res (div2 (- n 1))))
    (let ((s (car res))
      (d (car (cdr res))))
    (try-iter (+ 1 (random (- n 1))) 0 (- s 1) d))))


(define (miller-rabin-fast-prime? n times)
  (cond ((= times 0) true)
        ((miller-rabin-test n) (miller-rabin-fast-prime? n (- times 1)))
        (else false)))

米勒-拉宾素性检验
还没有完成, 需要迭代出r∈[1, s - 1]
已经完成

scheme

学习语法要多久左右？

@Cococ 用不了一周