Skip to content

Instantly share code, notes, and snippets.

@shegeley
Created February 10, 2022 04:25
Show Gist options
  • Save shegeley/714c6bac9d2af75654dde60403923b64 to your computer and use it in GitHub Desktop.
Save shegeley/714c6bac9d2af75654dde60403923b64 to your computer and use it in GitHub Desktop.
Some clojure drafts on Coursera Cryprography I course.
(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)]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment