(define (square x) (* x x))
(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))))

本来x*y%m=b*d%m=((x%m)*(y%m))%m

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

这里设

x

y=a*m+b

x*y%m=(a*m*x+b*x)%m=b*x%m=(x*(y%m))%m得证