#| BEGIN (Введите свое решение) |#
(define (square x)
  (* x x))

(define (expmod-check base exp m)
  (define (mod-m x)
    (remainder x m))
  
  (define (remainder-of-square-check n)
    (if (and (= 1 (mod-m (square n)))
             (not (= n 1))
             (not (= n (- m 1))))
        0
        (mod-m (square n))))

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

(define (miller-rabin n)
  (define (try-it a)
    (= (expmod-check a n n) a))
  (try-it (+ 1 (random (- n 1)))))

(define (fast-prime? n times)
  (or (= times 0)
      (and (miller-rabin n)
           (fast-prime? n (- times 1)))))

(define (miller-rabin-test n)
  (if (even? n)
      (= n 2)
      (fast-prime? n 20)))
#| END |#