컴퓨터 보안 - 정수론

정수론?
숫자의 성질을 탐구

• 정수의 성질: 소수, 합성수
• 나눗셈: 유클리드 알고리즘, 나머지 정리
• 모듈러 산술: 특정 수로 나눈 나머지를 이용한 산술
• 디오판틴 방정식
• 정수론의 응용

<리만 가설>
소수의 분포: 수학적으로 분석하고자 함

소인수 분해

• 제곱근 계산: 2부터 루트 n까지를 범위로 한다
• 2부터 시작하여 각 정수 i에 대해 n을 i로 나눈다.
• 나누어 떨어지면 i는 n의 인수이다.
• n을 n/i로 업데이트 해서 계속해서 나눗셈을 진행한다.
• 이 과정을 i가 루트n을 초과할때까지 한다
• 시간 복잡도: O(2^i)

서로소 : 두 수가 공통적인 소인수를 갖지 않는 상태

모듈러 연산 : 나머지 연산

• a mod b : a를 b로 나눈 나머지

모듈러 연산자 특성

• [(a mod n) + (b mod n)] mod n = (a+b) mod n
• [(a mod n) * (b mod n)] mod n = (a*b) mod n

모듈러 연산의 항등원과 역원

• 항등원 : 어떤 원소와 연산을 해도 자기 자신이 되게 하는 원소
• 역원 : 특정 원소와 결합했을때 항등원을 생성하는 원소

페르마 정리

• 만약 p가 소수라면 a는 p에 의해 나누어지지 않는 양의 정수이면, 다음이 성립한다.
• a^(p-1) = 1 mod p
  의미: a^(p-1)을 p로 나누면 나머지가 1이됨
  ex) a=5 , p=13

마찬가지로

• a^p = a mod p가 된다. (p는 소수 a는 p로 나눠지지 않는 양의 정수)

오일러 Toitent 함수

확장된 유클리드 알고리즘

<유클리드 알고리즘>

• GCD(a,b) = GCD(b,a mod b)
• ex) GCD(55,22) = GCD(22,11) = GCD(11,0) = 11

 def gcd(int a, int b): 
  if(b==0):
  	return a
  return gcd(b,a%b)

<유클리드 알고리즘 역원>

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0  # gcd, x, y
    else:
        gcd, x1, y1 = extended_gcd(b, a % b)
        x = y1
        y = x1 - (a // b) * y1
        return gcd, x, y