Shor's algorithm, classical part

shors-test.clj

(ns shors.core
  (:require [clojure.math.combinatorics :as c]
            [clojure.test :as t :refer [is deftest]]))

(def tries (atom 0))

(defn test-val
  "Given p - 1, check whether p is a factor of n. Returns q if it is."
  [n p-1]
  (swap! tries inc)
  (let [p (inc p-1)]
    (when (zero? (mod n p))
      (/ n p))))

(defn factor-sequences
  "Return a systematic series of combinations of the factors"
  [factors]
  (lazy-seq
   (rest
    (apply concat
           (map (partial c/selections factors)
                (range 10))))))

(defn find-p-q [n factors]
  (reset! tries 0)
  (let [all-seqs (factor-sequences factors)]
    (loop [seqs all-seqs]
      (let [cur-seq (first seqs)
            p-1 (apply *' cur-seq)]
        (if-let [result (or (test-val n p-1)
                            (> p-1 n))] ; short-circuit
          [(inc p-1) result (str "tries: " @tries)]
          (recur (rest seqs)))))))

;;; tests:
(and (is (= (find-p-q 35 [2 3])
            [5 7 "tries: 3"]))
     (is (= (find-p-q 899 [2 3 5 7])
            [29 31 "tries: 24"]))
     )