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

(define (square-mrt base m)
  (if (and (not (or (= base 1) (= base (- m 1))))
           (= (remainder (square base) m) 1))
      0
      (remainder (square base) m)))

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

(define (miller-rabin-test n)
  (define (try-it a)
    (= (expmod-mrt a (- n 1) n) 1))
  (try-it (+ 1 (random (- n 1)))))
#| END |#