User Tools

Site Tools


study:algorithms:number_theory

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

study:algorithms:number_theory [2019/02/04 14:26] (current)
Line 1: Line 1:
 +====== 1. Elementary number-theoretic notions ​ ======
  
 +유클리드 정리
 +
 +gcd(a, b) = gcd (b, a mod b)
 +
 +
 +확장 유클리드 정리
 +
 +ax+by=gcd(a,​b)
 +
 +<​code>​
 +(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))])))
 +</​code>​
 +
 +
 +====== 2. Greatest common divisor ​ ======
 +
 +최대 공배수(Greatest Common Divisor)
 +
 +<​code>​
 +(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))))))
 +</​code>​
 +====== 3. Modular arithmetic ​ ======
 +
 +모듈라 연산(Modular arithmetic)
 +
 +<​code>​
 +(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))))
 +</​code>​
 +====== 4. Solving modular linear equations ​ ======
 +
 +모듈라 선형 방정식 풀이(Solving modular linear equations)
 +
 +<​code>​
 +(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)))))
 +</​code>​
 +====== 5. The Chinese remainder theorem ​ ======
 +
 +중국인 나머지 정리(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
 +                        ​
 +
 +<​code>​
 +(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))))))
 +</​code>​
 +
 +
 +[[http://​en.wikipedia.org/​wiki/​RSA_(algorithm)]]
 +
 +[[http://​navercast.naver.com/​contents.nhn?​rid=22&​contents_id=1404]]
 +====== 6. Powers of an element ​ ======
 +
 +거듭 제곱(Powers of an element)
 +
 +<​code>​
 +(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)))
 +</​code>​
 +====== 7. The RSA public-key cryptosystem ​ ======
 +
 +RSA 공개키 암호 시스템(The RSA public-key cryptosystem)
 +
 +
 +==1. p와 q라고 하는 두 개의 서로 다른 소수를 고른다.==
 +==2. 두 수를 곱하여 N=pq 를 찾는다.(modulus)==
 +==3. φ(N) = (p-1)(q-1) 를 구한다.(totient)==
 +==4. φ(N) 보단 작고, φ(N)와 서로소인 정수 e를 찾는다.==
 +==5. 확장된 유클리드 호제법을 이용하여 d * e를 φ(N)로 나누었을 때 나머지가 1인 정수 d를 구한다.(de ≡ 1 (mod φ(N))==
 +
 +
 +<​code>​
 +(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)))
 +</​code>​
 +
 +<​code>​
 +(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)))
 +</​code>​
 +
 +[[http://​ko.wikipedia.org/​wiki/​RSA_%EC%95%94%ED%98%B8]]
 +
 +[[https://​github.com/​topher200/​rsa-cryptography]]
 +====== 8. Primality testing ​ ======
 +
 +소수성 테스트(Primality testing)
 +
 +<​code>​
 +(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)))))
 +</​code>​
 +====== 9. Integer factorization ​ ======
 +
 +정수 인수분해(Integer factorization)
 +
 +<​code>​
 +(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))))
 +</​code>​
study/algorithms/number_theory.txt · Last modified: 2019/02/04 14:26 (external edit)