모듈식 산술은 특정 값에 도달하면 숫자가 "래핑(wrap around)"되는 정수에 대한 산술 구조입니다. 모듈식 산술을 사용하면 가장 현대적인 공개 키 암호 시스템의 기본 구성 요소인 그룹, 링 및 필드를 간단히 만들 수 있습니다.
예를 들어, Diffie-Hellman은 소수 pp로 정수의 곱셈 그룹이 필요합니다. 작동할 수 있는 여러 그룹이 있습니다. 모듈러 또는 시계 산술은 모듈로 N이 아닌 원에 대한 산술이며 0에서 N-1까지 12개의 전체 숫자만 사용할 수 있습니다.
모듈식 산술은 몇 가지 기본 연산에 대한 알고리즘 방법에서 매우 잘 알려져 있습니다. 이것이 대칭 키 암호화에서 유한 필드(AES)를 사용할 수 있는 이유 중 하나입니다. 암호화에는 복잡한 문제가 필요했습니다. 일부 문제는 모듈식 산술로 어려운 문제로 발전합니다.
예를 들어, 로그는 단순히 모든 정수에 대해 계산하기 위한 것이지만 모듈식 축소를 도입할 수 있을 때 계산하기 어려워질 수 있습니다. 뿌리를 발견하는 것과 유사합니다. Mod-arithmetic은 암호화의 핵심 수학 용어입니다.
현대 정수론의 대부분과 일부 실용적인 문제는 모듈식 산술과 관련이 있습니다. 산술 모듈로 N에서는 N의 부과 배수로 변하는 모든 숫자를 인식할 수 있는 정수에 대한 산술과 관련이 있습니다. 즉,
x=y mod N if x =y +mN for some integer m.
이 인식은 모든 정수를 N개의 동일한 클래스로 나눕니다. 일반적으로 숫자 0, 1, ….N-1과 같은 가장 단순한 구성원으로 이를 나타낼 수 있습니다.
a가 정수이고 n이 양의 정수인 경우 a를 n으로 나눈 나머지가 되도록 mod n을 나타냅니다. 그런 다음 $\mathrm{a\, =\, \left \lfloor a/n\right \rfloor\, x\, n\, +\, \left ( a\, mod\, n \right );}$
예 - 11 모드 7 =4
정리 - n은 정수에 대한 등가 관계입니다. 등가 클래스에는 n으로 나눈 나머지가 동일한 정수가 포함됩니다. 등가 클래스는 모듈로 n 합동 클래스라고도 합니다. 대신에 정수 a와 b는 동등하며 모듈로 n이 합동이라고 말할 수 있습니다.
모듈로 n에 합동인 모든 정수의 집합을 잔류 클래스 [a]라고 합니다.
모듈로 연산자에는 다음과 같은 속성이 있습니다. -
-
a ≡ b mod n if n|(a − b).
-
(a mod n) =(b mod n)은 a ≡ b mod n을 의미합니다.
-
a ≡ b mod n은 b ≡ a mod n을 의미합니다.
-
a ≡ b mod n 및 b ≡ c mod n은 a ≡ c 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) x (b mod n)] mod n =(a x b) mod n
Zn ={0, 1, 2,…
| 속성 | 표현식 |
|---|---|
| 교환 법칙 | (w + x) 모드 n =(x + w) 모드 n |
| 연관법 | (w x x) 모드 n =(x x w) 모드 n |
| | [(w + x)+y] 모드 n =[w+(x+y)] 모드 n |
| 분배법 | [(w x x) x y] 모드 n =[w x (x x y)] 모드 n |
| 신원 | [(w x (x + y)] mod n =[(w x x) + (w x y)]mod n |
| | (0 + w) 모드 n =w 모드 n |
| 덧셈 역수(-w) | (1 x w) 모드 n =w 모드 n |
| | 각 w ∈ Zn에 대해 w + z ≡ 0 mod n이 되도록 z가 존재합니다. |