;;; Helper functions:
(defun pairwise-multiply (pair1 pair2)
    (let ((ac (* (first pair1) (first pair2)))
            (ad (* (first pair1) (second pair2)))
            (bc (* (second pair1) (first pair2)))
            (bd (* (second pair1) (second pair2))))
         (list (+ ac ad bc) (+ ac bd))))

;;; If you're going for values well above n=1000000 (and maybe some more),
;;; you might want to consider making this function tail-recursive, or make
;;; the iterative version.
(defun pairwise-pow (pair n)
    ;; It's an error having n < 1, you may want to change this to check for
    ;; that condition.
    (cond
        ((= n 1) pair)
        ((evenp n) (let ((result (pairwise-pow pair (truncate (/ n 2)))))
                        (pairwise-multiply result result)))
        (t (let ((result (pairwise-pow pair (truncate (/ n 2)))))
                (pairwise-multiply pair (pairwise-multiply result result))))))

(defun fibonacci (n)
    (if (zerop n) 0
        (first (pairwise-pow '(1 0) n))))

;; Try this one, don't worry, it won't take you a millisecond.
(fibonacci 10000)