유클리드 정리

gcd(a, b) = gcd (b, a mod b)

확장 유클리드 정리

ax+by=gcd(a,b)

(defn extended-gcd
  [a b]
  (if (= b 0)
    [1 0]
    (let [[q r] (division-with-remainder a b)
          [s t] (extended-gcd b r)]
      [t (- s (* q t))])))

최대 공배수(Greatest Common Divisor)

(defn gcd "(gcd a b) returns the greatest common divisor of a and b" [a b]
  (if (or (not (integer? a)) (not (integer? b)))
    (throw (IllegalArgumentException. "gcd requires two integers"))  
    (loop [a (abs a) b (abs b)]
      (if (zero? b) a,
	  (recur b (mod a b))))))

모듈라 연산(Modular arithmetic)

(defn mod
  "Modulus of num and div. Truncates toward negative infinity."
  {:added "1.0"}
  [num div] 
  (let [m (rem num div)] 
    (if (or (zero? m) (pos? (* num div))) 
      m 
      (+ m div))))

모듈라 선형 방정식 풀이(Solving modular linear equations)

(defn modular-multiplicative-inverse
  "Determines the inverse cooresponding to a given a with respect to modules m."
  [a m]
  (let [[x y] (extended-gcd a m)]
    (big-integer (int (mod x m)))))

중국인 나머지 정리(The Chinese remainder theorem)

물건이 몇 개 있는지 총수는 알 수 없다.

다만, 3개씩 세면 2개가 남고 5개씩 세면 3개가 남고

7개씩 세면 2개가 남는다고 한다. 총수는 얼마인가?

70 : 5와 7의 공배수 중에서 3으로 나누면 나머지가 1인 가장 작은 수

21 : 3과 7의 공배수 중에서 5로 나누면 나머지가 1인 가장 작은 수

15 : 3과 5의 공배수 중에서 7로 나누면 나머지가 1인 가장 작은 수

105 : 3, 5, 7의 최소 공배수

70*1+21*2+15*3-105=52

(defn generate-encrypt-key
  "Determines a prime encrypt key (e) that satisfies:
     A. 1 < e < totient
     B. coprime to the totient
   First tries some common ones, then uses random primes."
  [totient]
  (let [check-e (fn [e totient] (and (coprime e totient) (< e totient)))]
    (condp check-e totient
      65537 65537
      17 17
      3 3
      (let [possible-e (find-prime (bit-length totient))]
        (if (check-e possible-e totient)
          possible-e
          (generate-encrypt-key totient))))))

http://en.wikipedia.org/wiki/RSA_(algorithm)

http://navercast.naver.com/contents.nhn?rid=22&contents_id=1404

거듭 제곱(Powers of an element)

(defn mod-pow
[b e m]
(let [f (fn [a b e]
 (if (<= e 0)
   a
    (let [t (if (= (bit-and e 1) 1) (mod (* a b) m) a)]
    (recur t (mod (* b b) m) (bit-shift-right e 1)))))]
    (f 1 b e)))

RSA 공개키 암호 시스템(The RSA public-key cryptosystem)

(defn generate-keys [bit-length]
  (let [[p q] (find-two-unique-primes bit-length)
        modulus (. p (multiply q))
        totient (generate-totient p q)
        encrypt-key (generate-encrypt-key totient)
        decrypt-key (modular-multiplicative-inverse encrypt-key totient)]
    (hash-map :modulus modulus :e encrypt-key :d decrypt-key)))

(defn encrypt-message-big-integer
  [message encrypt-key modulus]
  (. message (modPow encrypt-key modulus)))

(defn decrypt-message-big-integer
  [message decrypt-key modulus]
  (. message (modPow decrypt-key modulus)))

http://ko.wikipedia.org/wiki/RSA_%EC%95%94%ED%98%B8

https://github.com/topher200/rsa-cryptography

소수성 테스트(Primality testing)

(defn prime? [n]
  (defn get-random-a []
    (long (+ 2 (random (- n 4)))))
  (defn test-value [a]
    (= (expmod a (- n 1) n) 1))
  (cond (= n 2) true
        (= n 3) true
        (= n 4) false
        (= n 5) true
        :else (and
               (test-value (- n 1))
               (test-value (- n 2))
               (test-value (get-random-a))
               (test-value (get-random-a))
             (test-value (get-random-a)))))

정수 인수분해(Integer factorization)

(defn prime-factorization [n]
 ;; we do not need to test prime factors larger than (+ 1 (Math/sqrt n))
 (let [stop (+ (Math/sqrt n) 1)]
  (defn prime-factorization-iter [k1 working]
   (let [answer (generate-factors k1 working)
         k2 (next-prime-factor k1)]
    (if (> k2 stop)
         answer
         (prime-factorization-iter k2 answer))))