1장. 정수론_소수

실습_1. 정수론_소수

• 수 그 자체에 대해 탐구하는 수학의 한 분야

모듈러 연산

• a mod b = c와 같이 표기
• a를 b로 나눈 나머지는 c
• 10 % 3 = 1

소수

소수의 정의

• 소수: 자신보다 작은 두개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수
• 합성수: 1보다 큰 자연수 중 소수가 아닌수

소수판별법

• 사람의 경우
  • 나누어떨어지는 수가 있으면 합성수
  • 모든 수가 ‘안 됨’을 확인하면 소수로 인정
• 컴퓨터의 경우
  • 2부터 n-1까지 차근차근 시도해본다(For Loop)
  • 중간에 나누어 떨어지는 수가 있으면 합성수 n-1까지 통과했으면 소수

에라토스테네스의 체

1. 찾고자 하는 범위의 자연수를 나열한다.
2. 2부터 시작하여, 2의 배수를 지워나간다.
3. 다음 소수의 배수를 모두 지운다.

소인수 분해

• 어떤 수를 소수들의 곱으로만 나타내는 것
• 소수는 그 자체고 이미 소인수 분해 완료된 수

현대암호와 소인수 분해

• 소인수 분해를 하는 과정 : 어려움

• 큰 소수로 합성수를 만드는 과정 : 쉬움

  색을 섞는것과 비슷하다
  - 두색을 섞는건 쉽지만 다시 분리해내는 것은 어렵다 
  

• 공개키 비밀키

  • 소인수 분해는 현대 암호학에 있어 매우 중요

    • 공개키와 비밀키를 조합해서 양쪽으로 서로 보낸다
    • 받는 공개키 + 비밀키 에 내가 가진 비밀키를 조합하면
    • 양쪽은 같은 정보를 공유한 것이다