04. 네 번째 수업: 비밀번호와 소인수분해 (Prime Factorization)

우리가 매일 쓰는 스마트폰 뱅킹, 인터넷 쇼핑몰 결제, 심지어 군대의 미사일 발사 통신망까지. 이 모든 디지털 세계의 정보는 단 하나의 수학적 행위 뒤에 숨어 철통처럼 보안을 유지하고 있습니다. 바로 ‘소인수분해’입니다.

학습 목표

• 크고 복잡한 합성수를 소수(Primes)들의 곱셈으로 처참히 해체해 버리는 소인수분해의 힘을 이해합니다.
• 가지치기(거꾸로 나눗셈) 방식을 통해 직관적으로 숫자의 유전자(Base parts)를 분리합니다.
• 파이썬의 반복 파괴 루프인 while문을 이용해 컴퓨터가 큰 숫자를 뼈가 보일 때까지 갉아먹는 해킹 로직을 코딩합니다.

1. 숫자의 유전자 지도: 소인수분해

앞선 수업에서 배운 ‘소수(Prime)’들이 우주의 가장 순수한 레고 블록($2, 3, 5, 7…$)이라면, 이 블록들을 조립($\times$)하여 만들어 낸 커다란 덩어리($18, 30…$)를 다시 원래의 레고 조각들로 인수분해(산산조각) 해버리는 작업이 바로 ‘소인수분해’입니다.

예를 들어 숫자 $60$의 영혼을 한번 탈탈 털어볼까요?

1. 짝수니까 만만한 소수 $2$로 먼저 반으로 가릅니다. $\rightarrow 2 \times 30$
2. 아직 뚱뚱한 $30$을 또 $2$로 가릅니다. $\rightarrow 2 \times 2 \times 15$
3. 남은 $15$는 만만한 $3$으로 가릅니다. $\rightarrow 2 \times 2 \times 3 \times 5$
4. 생존한 $2, 3, 5$는 모두 다이아몬드 소수입니다. 해체 끝!

수학자들은 똑같은 $2$가 두 번 곱해진 것을 예쁘게 요약하여 ‘거듭제곱’을 씌워줍니다.

$\mathbf{60 = 2^2 \times 3 \times 5}$

이것이 바로 $60$이라는 숫자가 숨기고 있던 완벽한 유전자(DNA) 지도입니다.

2. RSA 암호 체계와 현대 해커들의 전쟁

그런데 겨우 숫자를 쪼개는 것이 어떻게 최첨단 비밀번호(Password) 역할을 할까요?

“두 소수 $A$와 $B$를 서로 ‘곱하는 것’은 컴퓨터로 1초 만에 풀 수 있지만, 이미 거대하게 곱해진 숫자 $C$ 덩어리를 다시 옛날 소수 $A, B$로 해체(소인수분해)하는 것은 우주 최강의 슈퍼컴퓨터로도 1,000년이 넘게 걸린다.”

바로 이 압도적인 ‘시간의 불균형성’을 이용해 전 세계의 은행 통신망을 보호하는 것이 가장 악명 높은 RSA 암호 시스템입니다! 여러분이 지금 이 글을 읽는 브라우저의 https 자물쇠 역시, 수십억 자리의 소인수분해의 방패막 뒤에 숨어 작동하는 것입니다.

3. Python 파괴 머신: While 무한 탈곡기

이제 파이썬(Python)의 끝없는 분해 톱니바퀴, while 루프를 사용해 저 RSA 암호문의 해킹 원리를 흉내 내 미세먼지 단위로 숫자를 갉아먹어(소인수분해) 보겠습니다.

# 파이썬으로 구현하는 해커들의 기본 도구 (DNA 소인수분해 분쇄기)

def prime_factorization(number):
    """큰 암호 덩어리를 소수 블록으로 끝까지 파먹는 무자비한 해체 엔진"""
    factors = []  # 뜯어낸 소수 뼈다귀들을 담을 그릇 (리스트)
    
    divider = 2   # 가장 작고 만만한 2번 톱니바퀴부터 분쇄를 시작
    
    # 덩어리가 1(뼈)이 되어 완전히 사라질 때까지 영원히 도는 'while' 분쇄기
    while number > 1:
        # 이 숫자가 당장 내가 돌리는 톱니(divider)에 쪼개진다면?
        if number % divider == 0:
            factors.append(divider)  # 뼈다귀 수거!
            number = number // divider  # 덩어리 크기를 박살 내어 줄입니다 (핵심 로직!).
        else:
            # 이 톱니(divider)로는 안 부서진다? 다음 톱니바퀴로 무기를 교체(+1)!
            divider += 1
            
    return factors

# 은행 데이터 서버의 암호(복잡한 합성수) 덩어리를 뜯어봅시다
bank_password_block = 1260

# 해킹 툴 가동.
dna_codes = prime_factorization(bank_password_block)

print(f"[타겟 암호]: {bank_password_block}")
print(f"--> [소인수분해 완료! 추출된 원시 DNA 배열]: {dna_codes}")
# 출력 결과: [2, 2, 3, 3, 5, 7]
# 거듭제곱 폼의 우아한 표기: 2^2 * 3^2 * 5 * 7

우리의 파이썬 코드는 숫자가 $1$이 되어 완전히 부서질 때까지(while number > 1), 똑같은 칼잡이(def prime_factorization)로 미친 듯이 내려쳐 숫자의 뿌리($2, 2, 3, 3, 5, 7$)를 완벽하게 해체해 냈습니다.

학습 정리

1. 소인수 (Prime Factor): 어떤 합성수를 구성하고 있는 가장 기본 물질, 즉 약수이자 동시에 소수인 성분들을 말한다.
2. 거듭제곱($a^n$): 똑같은 소인수 블록이 여러 개 겹쳐 나올 때 지붕(지수)에 합쳐서 우아하게 렌더링하는 기호 표시법.
3. 파이썬의 While(조건문) 루프는 목표 조건이 박살 날 때까지 톱니크기를 조절하며 루틴을 끝없이 반복시키는 최고의 데이터 해체 머신이다.