The Miller-Rabin Primality Test in Clojure
There is an error in the translation of the probablyPrime function. In Clojure, a function body is an implicit do form. The two if forms and  the cond form: 

(defn probablyPrime [p accuracy upto]
  (if...
    )

  (if ...
    )

  (cond
    ...
    ))


... will be evaluated in succession. The values of the (if ...)s will be discarded; the result of the (cond ...) will be returned. The Python returns the associated value if either if condition is satisfied. 

For example, the Clojure gives 

(probablyPrime -2 0 1)
;true


... whereas the Python returns false. 

I suggest you bring all the conditions under the cond:  

(defn probablyPrime [p accuracy upto]
  (cond
    (or (= p 2) (= p 3)) true
    (&lt; p 2) false
    (&gt; upto accuracy) true
    (isWitness (rand-between (- p 2)) p (:exponent (decompose 0 (- p 1))) (:n (decompose 0 (- p 1))) 0) false
    :else (probablyPrime p accuracy (inc upto))))




There are other problems that make your Clojure unworkable for testing large numbers: 


You use proper recursion to express Python for loops. This may
cause stack overflow and will certainly slow things down. Use
Clojure's recur instead.
Your rand-between function is \$\mathcal{\Theta}(n)\$. This is a performance
disaster when \$n\$ is huge.




There are also some constructions that would improve your code in small ways: 


Use let forms to avoid recalculating expressions.
Use inc and dec instead of (+ ... 1) and (- ... 1). 
Prefer explicit arities to rest parameters in function pow.


With these improvements, the rest of the code now looks as follows: 

(ns miller-rabin.core
  (:gen-class)
  (:require [clojure.math.numeric-tower :as math]))

(defn pow
  ([x y] (math/expt x y))
  ([x y z] (mod (pow x y) z)))

(defn rand-between [n]
  (+ (rand-int (- n 2)) 2))

(defn decompose [exponent-of-two n]
  (if (odd? n)
    {:exponent exponent-of-two :n n}
    (recur (inc exponent-of-two) (quot n 2))))

(defn checkWitness [possibleWitness p exponent remainder upto]
  (let [possibleWitness (pow possibleWitness 2 p)]
    (or
     (&gt; upto exponent)
     (and
       (not= (dec p) possibleWitness)
       (recur possibleWitness p exponent remainder (inc upto))))))

(defn isWitness [possibleWitness p exponent remainder upto]
  (let [possibleWitness (pow possibleWitness remainder p)]
    (cond
     (or (= possibleWitness 1) (= possibleWitness (dec p))) false
     (zero? exponent) true
     :else (checkWitness possibleWitness p exponent remainder upto))))




I've noticed that, in translation, several functions have acquired an extra argument that is used internally to control repetition. I'll just restore decompose: 

(defn decompose [n]
  (loop [exponent-of-two 0, n n]
    (if (odd? n)
      {:exponent exponent-of-two :n n}
      (recur (inc exponent-of-two) (quot n 2)))))


The others - isWitness and probablyPrime  - are up to you. If you follow the Python, you don't need to factor out checkWitness. 



To do: 


I have not seriously tested the above.
Factoring out checkWitness from isWitness can be bettered using
the sequence library.