(defun expt-mod (x n z)
  (let ((r (expt x 0)))
    (dotimes (i (integer-length n) r)
      (setf r (mod (expt r 2) z))
      (if (eql (ldb (byte 1 (- (1- (integer-length n)) i)) n) 1)
          (setf r (mod (* r x) z))))))

(defun expt-mod2 (x n z)
  (let ((r (expt x 0)))
    (dotimes (i (integer-length n) (mod r z))
      (setf r (expt r 2))
      (if (eql (ldb (byte 1 (- (1- (integer-length n)) i)) n) 1)
          (setf r (mod (* r x) z))))))

(defun expt-mod3 (x n z)
  (let ((r (expt x 0)))
    (dotimes (i (integer-length n) r)
      (setf r (mod (expt r 2) z))
      (if (eql (ldb (byte 1 (- (1- (integer-length n)) i)) n) 1)
          (setf r (* r x))))))

(defun expt-mod4 (x n z)
  (let ((r (expt x 0)))
    (dotimes (i (integer-length n) (mod r z))
      (setf r (expt r 2))
      (if (eql (ldb (byte 1 (- (1- (integer-length n)) i)) n) 1)
          (setf r (* r x))))))

;; CL-USER> (time (expt-mod #x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
;;                          #xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140
;;                          #xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F))
;;
;; Evaluation took:
;;   0.000 seconds of real time
;;   0.000770 seconds of total run time (0.000672 user, 0.000098 system)
;;   100.00% CPU
;;   835,852 processor cycles
;;   147,200 bytes consed
;;
;; 111397357172144804920169018646854829611493432618108526724950070695867774004363
;; CL-USER> (time (expt-mod2 #x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
;;                           #xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140
;;                           #xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F))
;; Evaluation took:
;;   0.004 seconds of real time
;;   0.004012 seconds of total run time (0.004012 user, 0.000000 system)
;;   100.00% CPU
;;   4,383,363 processor cycles
;;   198,192 bytes consed
;;
;; 111397357172144804920169018646854829611493432618108526724950070695867774004363
;; CL-USER> (time (expt-mod3 #x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
;;                           #xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140
;;                           #xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F))
;; Evaluation took:
;;   0.000 seconds of real time
;;   0.001031 seconds of total run time (0.001031 user, 0.000000 system)
;;   100.00% CPU
;;   1,118,187 processor cycles
;;   147,120 bytes consed
;;
;; 111397357172144804920169018646854829611493432618108526724950070695867774004363
;; CL-USER> (time (expt-mod4 #x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
;;                           #xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140
;;                           #xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F))
;; takes forever