별 잡다

정수론

pwerty 2025. 3. 20. 15:36

정수론은 수학에서 원래 수학에서 다루던 이야기인데, 자연수에 대한 깊이 있는 내용을 다룬다.
많은 알고리즘 문제와 관련이 있고, 실무에서도 자주 사용된다.
아래에 설명 할 것은 정수론 내에 어떤 부분이 주로 고려 대상인지에 대해 논한다.

  • 소수 판별
    • 에라토스테네스의 체 (Sieve of Erathosthenes)
      자연수 n이 주어지면 1-n까지를 모두 배열에 깔아놓고, n까지의 소수들을 구한다. 소수의 배수는 100% 소수가 아닌 것이니 지운다. 1은 이도저도 아니니 지운다. 이렇게 하면 1-n까지의 모든 소수를 구 할 수 있다. 현재까지는 이게 제일 빠르다.
    • 소인수 분해
      • 주어진 수를 소수들의 곱으로 분해하는 방법으로, 암호학에서 주로 많이 사용된다.. 라고 설명하고 있다. RSA 암호화 알고리즘에서 사용한다는데 이 부분에 대해서 굳이 찾아보니 :

RSA는 두 개의 큰 소수를 곱해서 더 큰 숫자를 만든다. 무지막지하게 큰 숫자를 만드는건 쉬울지 몰라도 원래 두 소수로 나누는 것은 매우 쉽지 않다. 이 원래를 통해 공개키와 개인키를 만들게 된다고 설명한다.

  • 최대공약수와 최소공배수
    • 이를 효율적으로 계산하는 방법을 여러 알고리즘에서 사용하고 있다. 대표적으로 유클리드 알고리즘이 있다 :

유클리드 알고리즘은 두 수의 최대공약수를 구하는 고전적인 알고리즘이다.
두 수 a, b가 주어지면 gcd(a b) = gcd(b, a%b)를 반복적으로 호출하여 최대공약수를 구한다.
시간 복잡도는 O(log(min(a,b)))이다.
최소 공배수는 (a * b) / gcd(a, b)로 구할 수 있다.

  • 모듈러 연산
    • 나머지를 다루는 거의 모든 것들이 여기에 묶인다.

나머지는 a mod b = a를 b로 나눈 나머지를 이렇게 말한다.
17 mod 5는 2이다. 17 % 5 = 2이다.

  • 곱셈에 대한 모듈러 연산은 이와 같은 규칙이 있다.예시..분배 법칙의 개념이 존재한다.
    이는 모듈러 연산을 적용 할 때 계산을 단순하게 만드는데 기여 할 수 있다.

(a + b) mod m = ((a mod m) + (b mod m)) mod m
(a * b ) mod m = ((a mod m) * (b mod m)) mod m

(7 * 10) mod 5 = ((7 mod 5) * (10 mod 5)) mod 5 우선 70 mod 5 는 0이다.
7 mod 5는 2이고 10 mod 5는 0이다. 그럼 2 * 0 이니 0 mod 5를 시도하게 되고 답은 0이다.

(a * b) mod m= ((a mod m) * (b mod m)) mod m

즉 두 수의 곱에 대해 모듈러 연산을 한 결과는 각 수에 대해 모듈러 연산을 한 후,
그 결과의 곱에 대해 다시 모듈러 연산을 한 것과 동일하다.