User Tools

Site Tools


  • Learn about Wiki
  • Lectures
  • Study
  • Tips
    • study:algorithms:number_theory

      1. Elementary number-theoretic notions

      유클리드 정리

      gcd(a, b) = gcd (b, a mod 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))])))

      2. Greatest common divisor

      최대 공배수(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))))))

      3. Modular arithmetic

      모듈라 연산(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 div))))

      4. Solving modular linear equations

      모듈라 선형 방정식 풀이(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)))))

      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의 최소 공배수


      (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."
        (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)
                (generate-encrypt-key totient))))))

      6. Powers of an element

      거듭 제곱(Powers of an element)

      (defn mod-pow
      [b e m]
      (let [f (fn [a b e]
       (if (<= e 0)
          (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)))

      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))
      (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)))

      8. Primality testing

      소수성 테스트(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)))))

      9. Integer factorization

      정수 인수분해(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)
               (prime-factorization-iter k2 answer))))
      study/algorithms/number_theory.txt · Last modified: 2019/02/04 14:26 (external edit)