mod   Modular Arthmetic   모듈러 연산, 모듈로 연산

(2017-03-01)

mod-2, modulo 2, Modulo-2, 모듈러-2 덧셈, 모듈러-2 곱셈, Modulo-2 연산, Modulo-n, 법 n 연산, Modulo operator, 모듈러 연산자

기초과학 1. 과학

수학
물리/화학
지구,천체 과학
생명과학
 > 수학기초수학
집합,논리
정수론(수론)
해석학(미적분 등)
대수학
확률/통계
수치해법
 > 정수론(수론) 1. 정수론
2. 절대값
3. 짝수,홀수,패리티

수의 구분
셈법(Counting)
나눗셈(가분성)
디오판투스 방정식
소수,최대공약수
합동
 > 합동 1. 합동
2. 모듈러 연산
3. 동치
4. 쌍대성

     
1. 모듈러 연산 (Modular Arthmetic, Modulo-n Operation) 이란?모듈로 n 연산
     - 0 부터 n-1 까지의 제한된 정수 n개 만을 사용하는 연산
        . 유한개 원소 만으로 산술 연산을 하는 것

  ㅇ 표기  :  ( mod n )  
     - 결과값이 항상 n 보다 작은 양의 정수 값이 됨 (0 포함)

  ※ 나머지 연산 이라고도 함                                ☞ 나눗셈관계식 참조
     - 어떤 수를 수 n(divisor,modulus)으로 나눠 그 나머지(residue)를 구하는 연산
        . 이 때 몫(quotient)은 전혀 관심을 두지 않고 오로지 나머지에 만 관심을 둠
           .. 2개의 입력(제수 및 피제수)과 하나의 출력(나머지)을 갖는 이항 연산


2. 모듈러 연산식 (합동식) 표기

  ㅇ  a ≡ b (mod n)

     -  b : 피제수(dividend) ← 입력
     -  mod : 모듈러 연산자(modulo operator) ← 연산자
     -  n : 법(法,Modulus,Divisor) ← 입력
     -  ≡: 합동(Congruence)
     -  a : 나머지(Residue,Reminder) ← 결과

  ※ 위 관계식은 아래 표현들과 동치/동등 임

     -  `정수 a,b의 차 (a - b)가 양의 정수 n 으로 나누어 떨어짐`
        .  즉,  n | (a - b)  (☞ 약수 참조)
     -  `정수 a,b가, 양의 정수 n 으로 나누었을 때, 같은 나머지를 갖음`
        .  즉,  a = p n + r, b = q n + r 
     -  `n을 법(法,Modulus)으로하여 a는 b와 합동`
        .  a is congruent to b modulo n
     -  a = b + k n  
        . 나눗셈관계식으로써, k는 임의 정수
     -  `n을 법으로하는 a와 n을 법으로하는 b와 같음`
        . (a mod n) = (b mod n)

  ㅇ 例)  2 ≡ 11 (mod 3)  또는  2 = 11 (mod 3) 
     -  11 이나 2 를 3 으로 나누면 나머지 2 가 되는 것이 같음 즉, 합동 임
     -  입력 11에 대해 3을 법으로하여 mod 연산을 하면, 출력은 2 


3. 모듈러-2 (Modulo-2)  덧셈 및 곱셈 연산

  ※ 기본적으로, 모듈러-2 나눗셈 연산에 기초함
     - 즉, 2로 나눈 나머지를 염두에 두고 계산하면 됨

  ㅇ 모듈러-2 덧셈 => XOR 게이트(배타적-OR 게이트)로 구현 가능

       

     - 특징   : 같으면 = 0, 다르면 = 1
        . 동일 비트이면 연산 결과가 0, 상이한 비트이면 연산 결과가 1

     - 항등원 : 0 (e ⊕ a = a ⊕ e = a)
     - 역원   : 0의 역원은 0, 1의 역원은 1 이 됨 (a ⊕ a-1 = a-1 ⊕ a = e)

  ㅇ 모듈러-2 곱셈 => AND 게이트로 구현 가능

        

     - 특징 : 하나라도 0 이면 = 0, 모두 1일 경우에 만 = 1

     - 항등원 : 0 (e ⊗ a = a ⊗ e = a)


4. 모듈러-n (Modulo-n)  덧셈 및 곱셈 연산

  ※ 기본적으로, 모듈러-2 연산의 확장이며,
     - n으로 나눈 나머지를 염두에 두고 계산함

  ㅇ 모듈러-n 덧셈
     - i (modulo-n addition) j = r 
        .  i + j를 n으로 나눈 나머지가 r

     - 例) 5 (modulo-7 addition) 3 = 1

  ㅇ 모듈러-n 곱셈
     - i (modulo-n multiplication) j = r 
        .  i x j를 n으로 나눈 나머지가 r

     - 例) 5 (modulo-7 multiplication) 3 = 1


[ 합동 ]1. 합동  2. 모듈러 연산  3. 동치  4. 쌍대성  

 
        최근수정     모바일웹     참고문헌