[암호학] 모듈로 연산(Modular Artimetic)

모듈로 연산(Modular Artimetic)

• 나머지를 구하는 연산을 의미

      - a mod n = r

      - a를 n으로 나눈 나머지는 r일 경우 위와 같은 식으로 표기. n은 모듈로라고 부르고 r은 나머지 라고 부른다.

      - a는 정수, n은 양의 정수, r은 0을 포함한 양의 정수

 

ex) 12 mod 11 = 1

      -12 mod 11 = 10 => 원래는 -1이나 음수가 되면 안되므로 모듈로 11을 더해서 10

 

 

합동 (Congruence)

• 어떤 수로 나눈 나머지가 같을 때 

      - 3 mod 12 = 3

       15 mod 12 = 3

       => 3 ≡ 15 (mod12). 3과 15는 모듈로 12에 대해서 합동이다. 

• 공역(Zn)

     - 어떤 함수를 적용하였을 경우 나올 수 있는 모든 값의 집합

     - 합동식에서 모듈로 연산자를 적용하여 나올 수 있는 전체 집합

     ex)  mod12를 적용할 경우 나올 수 있는 값의 집합은 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}

 

모듈로 연산의 특성 

• (a+b) mod n = ((a mod n) + (b mod n)) mod n
• (a-b) mod n = ((a mod n) - (b mod n)) mod n
• (a×b) mod n = ((a mod n) × (b mod n)) mod n

       ex) 10^m mod n = (10 mod n)^m mod n 

      10^m mod 9 = (10 mod 9) ^m mod n = 1

 

역원

• a와 e를 연산한 결과가 a가 될 때 e를 항등원이라고 하고, a 와 a^-1을 연산한 결과가 e가 될 때 a^-1을 연산에 대한 a의 역원이라 한다. 

ex)

     덧셈에 대한 역원

      3+e = 3 => 항등원 e는 0

     덧셈에 대한 3의 역원은 -3 이다.

 

    곱셈에 대한 역원

    3×e = 3 => 항등원은 1

    곱셈에 대한 3의 역원은 1/3 => 유리수에서는 역원이 존재하지만 정수 범위 내에서는 역원이 존재하지 않는다. 

 

   모듈로 연산에 대한 역원

    a × a^1 = 1 mod n

    a의 모듈로 연산에 대한 역원은 a 와 n이 서로소 일 때 존재한다.

    => gcd(a, n) = 1 a와 n의 최대공약수가 1

   ex) (1 × □) mod 5 = 1 => 6 

         (2 × □) mod 5 = 1  => 3      

         (3 × □) mod 5 = 1  => 2

         (4 × □) mod 5 = 1  => 16

         (5 × □) mod 5 = 1  => X

         gcd(1,5) = 1,  gcd(2,5) = 1, ...

         but gcd(5,5) = 5 가 되므로 역원이 존재하지 않는다.