수학 빅넘 연산에서 LCM( P-1, Q-1) 값 구하는 법

LCM은 두수의 최소 공배수 이다. 이건 간단한 산수 이지만 실제로 적용할때는 어려워 보여서 한번 정리한다

RSA 암호에서 소수 P와 Q를 사용하여 개인키 D를 구할 때,
P−1과 Q−1의 최소공배수(LCM)을 이용한다.

빅넘 연산을 할때 아래 공식을 이용하여 계산 한다

$$ LCM(P-1,Q-1) = \frac { (P-1) \times (Q-1) } { GCD( P-1, Q-1) } $$

여기서:

• P와 Q는 두 개의 소수입니다.
• P−1과 Q−1은 각각 P와 Q에서 1을 뺀 값입니다.
• GCD(P−1,Q−1) 는 P-1과 Q-1 의 최대공약수(Greatest Common Divisor)를 의미한다.

예를 들어, P=11, Q=7일 때:

1. P−1=10, Q−1=6
2. GCD(10,6) = 2 (최대공약수)
3. LCM(10,6) = (10 x 6 ) / 2 = 30

따라서 LCM(P−1,Q−1) = 30 이다

RSA에서 P와 Q는 개인키 생성에 사용되며, LCM(P−1,Q−1)은 모듈러 연산을 설정하는 데 활용된다.