Modular Arithmetic

비유적으로 Clock arithmetic

- 나누기한 값의 나머지를 말함 ( mod = 나머지. //// 'x mod n' = 나머지. )

- 시계 7시 + 6시해도 13시아니고 1시이듯 0~5까지 6가지 경우 -> Clock Arithmetic

#Notation

· 7 mod 6 = 1

· 7 = 13 = 1

· ((a mod n) + (b mod n)) mod n = (a+b) mod n

· ((a mod n)(b mod n)) mod n = ab mod n

 

· (7 + 12) mod 6 = 19 mod 6 = 1 mod 6
· (7 + 12) mod 6 = (1 + 0) mod 6 = 1 mod 6

 

Modular Multiplication

· 3*4 = 0 ( mod 6 )

· 4*2 = 2 ( mod 6 )

· 5*5 = 1 ( mod 6 )

· 7*4 mod 6 = 28 mod 6 = 4 mod 6

 

Modular Inverses

· x mod n의 additive inverse (덧셈에 대한 역원) ( -x mod n) 은 x mod n에서  0 mod n을 얻기 위해 더해져야 하는 값.

(-2 mod 6 = 4 since 2 + 4 = 0 mod 6)

 

· x mod n의 multiplicative inverse (곱셈에 대한 역원) ( x^-1 mod n)는 x mod n에서 1 mod n 을 얻기 위해 곱해져야 하는 값.

(3^-1 mod 7 = 5, since 3 ⋅ 5 = 1 mod 7)

 

 

* Multiplicative inverse는 존재하지 않을 수도 있다.

EX) 2^-1 mod 6 

 

 

Relatively Prime (서로소) = 1 외에 공약수를 갖지 않는 두 정수

x^-1 mod y (multiplicative inverse)는 두 수가 서로소 일때만 존재한다.

 

 

Totient Function

ϕ(n)은 n보다 작고 n과 서로소 관계인 정수의 갯수를 말한다.

예) ϕ(5) = 4.. 1,2,3,4와 서로소

ϕ(4) = 2 .. 1,3과 서로소

ϕ(12) = 4 .. 1,5,7,11과 서로소

ϕ(p) = p-1 if p가 소수 일때

ϕ(pq) = (p-1)(q-1) if p와 q가 소수일때