(ns lab4.core)

(defn divides?
  "Проверка делимости числа нацело"
  [k n]
  (zero? (mod k n)))

(defn prime?
  "Проверка числа на простоту"
  [x]
  (or (= 2 x)
      (= 3 x)
      (and (< 1 x)
           (odd? x)
           (not-any? (partial divides? x)
                     (range 3 (inc (Math/sqrt x)) 2)))))

(defn mod-expt
  "Возведение в степень по модулю"
  [base, n, modulus]
  (loop [c 1
         inx-n 0]
    (if (= n inx-n)
      c
      (recur (mod (* c base) modulus)
             (inc inx-n)))))

(defn gcd
  "Алгоритм Евклида для нахождения НОД"
  [a b]
  (if (zero? b) a (recur b (mod a b))))

(defn ext-gcd
  "Расширенный алгоритм Евклида. Возвращает
  x и y уравнения a*x + b*y = gcd(a b)"
  [a b]
  (let [a (Math/abs a)
        b (Math/abs b)]
    (cond
      (zero? a) {:gcd b, :x 0, :y 1}
      (zero? b) {:gcd a, :x 1, :y 0}
      :else (loop [x 0, x0 1
                   y 1, y0 0
                   r b, r0 a]
              (if (zero? r)
                {:gcd r0, :x x0, :y y0}
                (let [q (quot r0 r)]
                  (recur (- x0 (* q x)) x
                         (- y0 (* q y)) y
                         (- r0 (* q r)) r)))))))

(defn m*
  "Вычисляет (p*q) mod m"
  [p q m]
  (mod (* p q) m))

(defn mod-inv-euclid
  "Вычисляет обратное число по модулю,
  используя расширенный алгоритм Евклида"
  [a m]
  (:x (ext-gcd a m)))

(defn solve-linear-congruence [mod-inv a b m]
  "Решает уравнение типа a*x = b(mod m).
  Возвращает список возможных решений"
  (let [d (gcd a m)]
    (when (zero? (mod b d))
      (let [m1 (/ m d)
            a1 (/ a d)
            b1 (/ b d)
            x0 (m* b1 (mod-inv a1 m1) m1)]
        (map #(+ x0 (* m1 %))
             (range d))))))

(defn encode->send->decode [p m]
  "Выполняет процедуру подписи сообщения и
  проверяет ее. Принимает простое число и хэш сообщения"
  (println "Next example: ")
  (let [X (rand-nth (range 2 p))
        G (rand-nth (range 2 p))
        Y (mod-expt G X p)
        K (rand-nth (filter #(= 1 (gcd % (dec p))) (range 2 p)))
        a (mod-expt G K p)
        arg (mod (- m (* a X)) (dec p))
        b (first (solve-linear-congruence mod-inv-euclid K arg (dec p)))
        to-send {:a a, :b b, :m m}
        check-num1 (mod (* (mod-expt Y a p) (mod-expt a b p)) p)
        check-num2 (* (mod-expt G m p))]
    (do
      (println "X: " X)
      (println "G: " G)
      (println "Y: " Y)
      (println "K: " K)
      (println "a: " a)
      (println "b: " b)
      (println "to-send: " to-send)
      (println "check-num1" check-num1)
      (println "check-num2" check-num2))))

(def primes ;; Расчет простых чисел до 10^6
  (filter prime? (range (Math/pow 10 6))))

(def p 199967) ;; Выбранное простое число

(def messages [67 34 16 87 105 76]) ;;Cписок хэшей сообщений

(map ;; Применяет главную функцию к каждому из хэшей сообщений
  (partial encode->send->decode p)
  messages)