정수론_NumberThoery

정수론_NumberTheory

• 정수의 성질을 다루는 수학의 한 분야이다.
• 우리가 왜 why? 공부해야 하는가
  • 현대 암호학은 주로 정수론에서 다루어지는 수학적인 성질을 바탕으로 하기에, 암호화 알고리즘을 이해하고 구현하기 위해서는 정수론에 대한 공부가 필요하다.
  • 컴퓨터에서 정수는 정확한 값을 가질 수 있다. 실수형 타입의 경우 반올림 오차(round off error)가 발생하기 때문에 이로 인한 문제가 발생할 수 있다.
• 정수와 자연수 소수를 중심적으로 다룬다.

소수_PrimeNumber

• 정수론에서 가장 중심적으로 연구하는 것
• 1과 자기 자신만을 약수로 가지는 수

에라토스테네스의 체

• 소수를 찾는 방법
• √n 까지의 배수를 지운다
• 노가다 방식이라 상당히 무식한 방식이지만 특정 범위가 주어지고 그 범위 내 모든 소수를 찾아야 하는 경우 에라토스테네스의 체보다 빠른 방법이 없다.

골드바흐 추측

• 4 이상의 모든 짝수는 두 소수의 합으로 나타낼 수 있다.
  • IBM에 무작정 대입 4~400경까지 모두 성립 but 수학적 증명법이 아니다. 결과일뿐 증명x

유클리드 호제법

• 두 양의 정수, 두 다항식에서 최대 공약수를 구하는 방법
• 두 양의 정수 a,b(a>b)에 대해 a = bq + r(0≤ r <b) 라면 a,b의 최대 공약수는 b,r의 최대 공약수와 같다. gcb(a,b) = gcb(b,r)
• r=0 이면 a,b 최대 공약수는 b가 된다.