Some clojure drafts on Coursera Cryprography I course.

crypro.clj

(ns cryptogroups.groups
  (:require [clojure.set :as set]))

(defn pow
  [x n]
  (Math/pow x n))

(defrecord Z [N])

(defrecord Z* [N])

(defrecord CyclicGroup
    [N generator])

(defn gcd [a b]
  (if (zero? b)
    a
    (recur b (mod a b))))

(defn in-group
  [group x]
  (let [N (get group :N)]
    (mod x N)))

(defn elements
  [group]
  (let [N (get group :N)
        r (vec (range 0 N))]
    (set
     (condp = (type group)
       Z r
       Z*
       (for [x r
             :when (= (gcd N x) 1)] x)
       CyclicGroup (let [g (get group :generator)]
                     (mapv #(mod (pow g %) N) r))
       (throw (Exception. (str "Can't operate on this type")))))))

(defn inverse
  [x group]
  (let [N (get group :N)
        els (sort (vec (elements group)))]
    (loop [i els]
      (if (empty? i) nil
          (let [m (* x (first i))
                mg (int (in-group group m))]
            (if (= 1 mg) (first i)
                (recur (rest i))))))))

(defn order
  [g N]
  (count (elements (CyclicGroup. N g))))

(defn euler-phi
  [N]
  (count (elements (Z*. N))))

(defn modular-root
  [^Integer x ^Integer power ^Z group]
  (let [init (quot x power)]
    (loop [i init]
      (cond
        (> (- i init) 100) (throw (Exception. (str "Seems like the modular root doesn't exists. Stopped after 100 iterations.")))
        (= x (int (in-group group (pow i power)))) i
        :else (recur (+ 1 i))))))

(defn d-log
  [x base ^Z* group]
  (loop [i 0]
    (let [r (in-group group (pow base i))]
      (if (= x (int r))
        i
        (recur (+ i 1))))))

(defn solve-quadratic-mod
  [a b c ^Z* group]
  (let [D (- (pow b 2) (* 4 a c))
        v1 (/ (- b (Math/sqrt D)) (* 2 a))
        v2 (/ (- b (- (Math/sqrt D))) (* 2 a))]
    [(in-group group v1)
     (in-group group v2)]))