- Learn about Wiki
- Lectures
- Study
- Tips
유클리드 정리
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)))
소수성 테스트(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))))