정수와 나머지 - 해시·암호·주기

이 장에서 배우는 것

작업을 여러 처리 칸에 나누어 넣거나, 일정한 간격으로 같은 위치를 다시 방문하는 코드를 작성하면 나머지 연산을 만나게 된다. 큰 정수의 거듭제곱을 다룰 때도 마지막에 필요한 값이 전체 정수가 아니라 어떤 수로 나눈 나머지인 경우가 있다. 이 장에서는 정수를 나누는 규칙에서 출발해, 계산 도중의 수를 작게 유지하는 방법까지 직접 구현한다.

앞 장에서 충돌을 확률로 살펴보았다면, 여기서는 서로 다른 정수가 같은 칸에 들어가는 계산 규칙을 확인한다. 정의를 먼저 외우기보다 작은 입력을 손으로 계산하고, 같은 과정을 반복문으로 옮긴다. 수학에서 허용되는 변형과 Python에서 실제로 실행되는 연산을 함께 살펴본다.

• 몫과 나머지가 원래 정수를 어떻게 복원하는지 설명한다.
• 최대공약수를 구하는 유클리드 호제법을 반복문으로 구현한다.
• 같은 나머지를 갖는 수끼리 더하거나 곱해도 되는 이유를 확인한다.
• 큰 거듭제곱의 나머지를 제곱과 반복으로 계산하고 Python의 pow와 비교한다.
• 처리 칸 배정과 순환 위치에서 최대공약수가 어떤 역할을 하는지 확인한다.

문제 상황

작업 번호를 받아 여덟 개의 처리 칸 중 하나에 배정하는 프로그램을 만든다고 하자. 처리 칸 번호는 0부터 7까지다. 작업 번호가 18이면 2번 칸에 넣고, 26도 2번 칸에 넣는다. 다음 코드처럼 나머지를 사용하면 번호가 커져도 칸 번호의 범위를 유지할 수 있다.

jobs = [18, 26, 34]
for job in jobs:
    print(job, job % 8)

세 줄의 결과는 각각 18 2, 26 2, 34 2다. 서로 다른 입력이 같은 칸으로 가는 일을 충돌이라고 부른다. 칸 번호가 유효하다는 사실과 작업이 고르게 나뉜다는 사실은 다르다. 이 입력들은 모두 8만큼 차이가 나므로 같은 칸에 모인다.

다른 요구도 생긴다. 열 개 위치를 가진 순환 목록에서 현재 위치에 4를 더하며 이동하려 한다. 위치를 벗어나면 처음으로 돌아가도록 나머지를 쓰면 된다. 그런데 이 방법은 열 개 위치를 모두 방문하지 않는다. 또한 어떤 계산에서는 7을 열세 번 곱한 값 자체보다 그 값을 11로 나눈 나머지만 필요하다. 세 문제 모두 나머지를 쓰지만, 올바른 코드를 작성하려면 각 연산이 보존하는 성질을 알아야 한다.

몫과 나머지로 정수를 나누기

나누기는 두 결과를 만든다

정수 a를 양의 정수 m으로 나누면 정수 q와 r을 이용해 다음과 같이 나타낼 수 있다. q는 몫이고 r은 나머지다. 전공 수업에서는 이처럼 몫과 나머지의 존재와 범위를 정하는 성질을 나눗셈 정리라고 부른다.

a = q × m + r, 0 ≤ r < m

예를 들어 23을 5로 나누면 23 = 4 × 5 + 3이다. 몫은 4이고 나머지는 3이다. 여기서 나머지의 범위는 부가 조건이 아니다. 범위를 정하지 않으면 23 = 3 × 5 + 8도 가능해져 몫과 나머지를 하나로 정할 수 없게 된다.

양의 수로 나눌 때 몫과 나머지는 원래 정수를 복원한다

a	m	몫 q, 나머지 r	복원
23	5	4, 3	4 × 5 + 3 = 23
20	5	4, 0	4 × 5 + 0 = 20
-7	5	-2, 3	-2 × 5 + 3 = -7

Python에서 정수의 //는 몫을, %는 나머지를 구한다. divmod(a, m)은 두 결과를 한 번에 돌려준다. 두 값을 q, r = divmod(a, m)처럼 받으면 각각의 변수에 몫과 나머지가 들어간다.

for a in [23, 20, -7]:
    q, r = divmod(a, 5)
    print(a, q, r)
    assert a == q * 5 + r
    assert 0 <= r < 5

assert는 뒤의 조건이 참인지 검사하는 문장이다. 거짓이면 실행을 멈추고 AssertionError를 알린다. 여기서는 프로그램을 읽는 사람이 계산 규칙을 직접 확인하도록 사용한다. 사용자 입력을 검사하는 용도로는 뒤에서 사용하는 if와 예외를 쓴다.

음수에서는 몫의 방향을 살핀다

-7을 5로 나눌 때 몫을 -1로 잡으면 나머지는 -2가 된다. 이 장에서 정한 나머지 범위에는 들어가지 않는다. Python은 //의 결과를 실제 나눗셈 값보다 크지 않은 가장 가까운 정수로 정한다. 이를 내림이라고 부른다. -1.4를 내리면 -2이므로 -7 // 5는 -2이고 -7 % 5는 3이다.

이 장의 나누는 수는 모두 양수다. Python은 음수로 나누는 연산도 지원하지만, 그때는 나머지가 양수일 때와 같은 범위를 갖지 않는다. 처리 칸 수나 순환 목록의 길이는 양수이므로, 여기서는 그 조건을 코드의 약속으로 삼는다. 0으로 나누는 연산은 정의하지 않는다.

그림에서는 5의 배수인 -10을 출발점으로 잡았다. 여기서 오른쪽으로 3만큼 이동하면 -7이다. 음수라고 해서 나머지까지 음수라고 예상하면 배열 위치를 계산하는 코드가 다른 언어와 다른 결과를 낼 수 있다. 언어를 옮길 때는 음수 입력을 작은 예제로 먼저 확인하는 편이 좋다.

최대공약수와 유클리드 호제법

공통으로 나눌 수 있는 가장 큰 단위

정수 d로 정수 a를 나누었을 때 나머지가 0이면 d가 a를 나누어떨어지게 한다고 말한다. 양의 정수 d에 대해 이때 d를 a의 약수라고 부른다. 두 수를 모두 나누어떨어지게 하는 양의 정수는 공약수다. 그중 가장 큰 수가 최대공약수(greatest common divisor)이며, 코드에서는 흔히 gcd라는 이름을 쓴다.

예를 들어 길이가 18과 30인 두 띠를 같은 길이의 조각으로 남김없이 자르려 한다. 조각 길이를 양의 정수로 제한하면 가능한 공통 길이는 1, 2, 3, 6이다. 그중 가장 큰 길이는 6이다. 작은 입력에서는 후보를 모두 확인할 수 있다.

common = []
for d in range(1, 19):
    if 18 % d == 0 and 30 % d == 0:
        common.append(d)
print(common)
print(max(common))

출력은 [1, 2, 3, 6]과 6이다. max는 목록에서 가장 큰 값을 고른다. 이 방식은 뜻을 확인하기에는 좋지만, 작은 쪽 수가 매우 크면 확인할 후보도 많아진다. 필요한 후보를 하나씩 찾는 대신 문제의 두 수 자체를 줄일 수 있다.

나머지로 바꾸어도 공약수는 같다

a = q × b + r라고 하자. 어떤 수 d가 a와 b를 모두 나누어떨어지게 하면 a에서 q × b를 뺀 r도 나누어떨어지게 한다. 반대로 d가 b와 r을 모두 나누어떨어지게 하면 q × b + r인 a도 나누어떨어지게 한다. 따라서 a와 b의 공약수 목록은 b와 r의 공약수 목록과 같다. 가장 큰 공약수도 같다.

gcd(a, b) = gcd(b, a % b)

이 성질로 두 수를 계속 교체하는 방법을 유클리드 호제법이라고 부른다. 252와 105에서 시작하면 다음과 같이 진행된다. 마지막으로 0이 아닌 나누는 수가 답이다.

나머지로 교체하면 같은 최대공약수를 가진 더 작은 문제를 얻는다

a	b	a % b	다음 두 수
252	105	42	105, 42
105	42	21	42, 21
42	21	0	21, 0

반복이 끝나는 이유도 나머지의 범위에 있다. b가 양수일 때 새 나머지는 0 이상이고 b보다 작다. 다음 나누는 수는 이전보다 작은 음이 아닌 정수가 된다. 이런 감소를 계속하면서 양수에 머물 수는 없으므로 결국 0을 만난다. 이때 gcd(a, 0)은 a다. 모든 양의 정수가 0을 나누어떨어지게 하므로, a와 0의 공약수는 a의 약수와 같기 때문이다.

구현에서는 입력에 abs를 적용해 절댓값, 즉 부호를 제외한 크기로 바꾼다. 그러면 음수 입력도 같은 규칙으로 처리한다. 두 입력이 모두 0이면 가장 큰 양의 공약수를 고를 수 없다. 이 프로그램은 Python의 math.gcd와 맞추어 gcd(0, 0)을 0으로 돌려주는 약속을 사용한다.

최대공약수가 1인 두 정수는 서로소라고 부른다. 이는 두 수가 모두 소수라는 뜻이 아니다. 8과 15는 각각 더 작은 수로 나누어떨어지지만 공통인 양의 약수는 1뿐이므로 서로소다. 다음 계산으로 확인할 수 있다.

from math import gcd

print(gcd(8, 15))
print(gcd(-18, 30))
print(gcd(0, 0))

출력은 순서대로 1, 6, 0이다. 완성 코드에서는 직접 만든 함수의 결과를 이 표준 라이브러리 함수와 비교한다. 이름이 같은 두 함수를 구별하도록 표준 함수에는 다른 이름을 붙인다.

같은 나머지로 계산을 줄이기

나머지가 같다는 관계

18과 26을 8로 나누면 나머지가 모두 2다. 두 수의 차이인 8도 8로 나누어떨어진다. 이렇게 두 정수의 차이가 m의 배수이면 두 수가 m을 법으로 합동이라고 부른다. 전공 수업에서 쓰는 ‘법’은 나머지를 구할 때 기준으로 삼는 양의 정수다. 이 장에서는 이를 나누는 수 m과 같은 뜻으로 쓴다.

합동인 수를 다룰 때는 원래 수를 그 나머지로 바꾸어도 덧셈, 뺄셈, 곱셈의 최종 나머지가 같다. 이런 계산을 모듈러 연산(modular arithmetic)이라고 부른다. 예를 들어 a = q × m + r, b = s × m + t라면 a + b는 (q + s) × m + r + t다. m의 배수 부분은 최종 나머지에 영향을 주지 않는다. 곱셈도 펼쳐 보면 r × t를 제외한 항에 m이 들어간다.

a, b, m = 18, 13, 8
print((a + b) % m, ((a % m) + (b % m)) % m)
print((a - b) % m, ((a % m) - (b % m)) % m)
print((a * b) % m, ((a % m) * (b % m)) % m)

출력은 차례대로 7 7, 5 5, 2 2다. 한 쌍의 예시만으로 모든 입력에서 성립한다고 결론 내리지는 않는다. 앞의 식이 성질의 근거이고, 코드는 구현 과정의 실수를 찾는 도구다. 완성 코드에서는 음수를 포함한 작은 범위 전체를 검사한다.

나눗셈까지 같은 방식으로 옮길 수 있는 것은 아니다. 2 × 1과 2 × 4는 6으로 나눈 나머지가 모두 2지만, 1과 4는 같은 나머지를 갖지 않는다. 양쪽에 공통으로 곱해진 2를 지우면 관계가 달라진다. 나머지를 다루는 식에서 곱셈을 취소하려면 별도의 조건이 필요하다. 이 장에서는 덧셈, 뺄셈, 곱셈과 음이 아닌 정수 지수만 사용한다.

거듭제곱을 만들기 전에 나머지를 취한다

a의 e제곱은 a를 e번 곱한 값이다. 지수 e가 0일 때는 곱셈을 시작하기 전의 값인 1로 정한다. 이 장의 함수도 이 규칙을 따르며, 밑이 0이고 지수도 0인 입력 역시 Python과 같이 1을 출발값으로 사용한다. 마지막 결과는 다시 m으로 나눈 나머지다.

(a ** e) % m은 뜻을 그대로 표현하지만, 나머지를 구하기 전에 거듭제곱 전체를 만든다. Python 정수는 값이 커지면 저장 공간도 늘어날 수 있으므로 계산 시간과 메모리를 함께 생각해야 한다. 곱할 때마다 나머지를 취하면 값의 크기를 줄일 수 있다. 여기에 지수를 절반씩 줄이는 방법을 더한다.

지수가 짝수이면 a의 e제곱은 (a × a)의 e/2제곱이다. 지수가 홀수이면 a 하나를 따로 곱한 뒤 남은 짝수 지수에 같은 처리를 할 수 있다. 매번 제곱하며 지수를 줄이므로 이를 반복 제곱법이라고 부른다. 반복문 한 번에서 지수를 2로 나눈 몫으로 교체하므로, 지수만큼 반복해서 곱하는 것보다 반복 횟수가 빠르게 줄어든다.

그림의 result는 지금까지 선택한 곱의 나머지이고 base는 이번에 곱할 후보의 나머지다. e가 홀수일 때만 result에 base를 곱한다. 그다음 base를 제곱하고 e를 절반으로 줄인다. 13, 6, 3, 1을 처리하고 나면 e는 0이 된다.

반복 도중에는 result × base의 e제곱을 m으로 나눈 나머지가 원래 목표와 같다는 관계가 유지된다. 이런 식으로 반복 전후에 계속 참인 관계를 불변식이라고 부른다. e가 홀수이면 base 하나를 result로 옮기고, 남은 짝수 부분은 제곱으로 묶는다. e가 0이 되면 남은 거듭제곱은 1이므로 result가 답이다.

시작값은 result = 1 % m이다. 특히 m이 1이면 가능한 나머지는 0뿐이므로 지수가 0이어도 결과는 0이어야 한다. 밑은 음수여도 되지만 지수는 음이 아닌 정수, m은 양의 정수로 제한한다. Python의 세 인자 함수 pow(a, e, m)도 큰 거듭제곱 전체를 먼저 만들지 않고 나머지를 계산한다. 이 장에서 만든 함수와 결과를 비교할 기준이다.

실무에서 만나는 곳

첫째는 해시 값으로 처리 칸을 정하는 상황이다. 해시는 입력을 정해진 규칙으로 어떤 값에 대응시키는 계산이다. 여기서는 작업 번호를 이미 얻은 정수 해시 값처럼 취급하고, 마지막에 % 8을 적용한다. 나머지는 칸의 범위를 맞추지만 입력의 규칙성을 없애지는 않는다. 입력이 8의 배수만큼 떨어져 있으면 같은 칸에 모인다. 칸을 고르게 쓰는 문제와 충돌 뒤 데이터를 구별하는 문제를 따로 다루어야 한다.

둘째는 순환 위치다. m개 위치에서 매번 step만큼 이동하면 출발점으로 돌아오는 데 필요한 이동 횟수는 m // gcd(m, step)이다. 돌아오려면 이동 횟수 k에 대해 k × step이 m의 배수가 되어야 한다. m과 step을 최대공약수로 나눈 두 수는 서로소이므로, 이를 만족하는 가장 작은 양의 k가 m // gcd(m, step)이 된다.

열 개 위치에서 4씩 이동하면 최대공약수가 2여서 다섯 번 만에 돌아온다. 방문 위치는 0, 4, 8, 2, 6이다. step을 3으로 바꾸면 최대공약수가 1이므로 열 개 위치를 모두 방문한다. 이 계산은 순환 목록을 건너뛰며 읽거나 반복 작업의 방문 범위를 점검할 때 쓸 수 있다.

셋째는 암호 계산이다. 일부 공개 키 암호에서는 큰 정수의 거듭제곱을 어떤 수로 나눈 나머지를 계산한다. 이 장의 함수는 그 산술 과정을 살펴보는 예제다. 실제 암호 기능에는 키 생성과 입력 형식뿐 아니라 실행 시간으로 정보가 드러나는 문제도 포함된다. 여기서는 지수에 따라 실행 경로가 달라지는 학습용 함수를 만들며, 실제 암호 기능은 검토된 전용 구현을 사용한다.

완성 코드

다음 내용을 main.py로 저장한다. 입력은 정수라고 가정하고, 함수가 지원하지 않는 지수와 나누는 수는 명시적으로 거절한다. 외부 패키지와 난수를 사용하지 않으므로 실행 결과는 매번 같다.

from math import gcd as standard_gcd


def gcd(a, b):
    a, b = abs(a), abs(b)
    while b != 0:
        a, b = b, a % b
    return a


def mod_power(a, e, m):
    if e < 0:
        raise ValueError("지수는 0 이상이어야 한다")
    if m <= 0:
        raise ValueError("나누는 수는 양수여야 한다")

    result = 1 % m
    base = a % m
    while e > 0:
        if e % 2 == 1:
            result = (result * base) % m
        base = (base * base) % m
        e //= 2
    return result


def main():
    print("[몫과 나머지]")
    for a in [23, 20, -7]:
        q, r = divmod(a, 5)
        assert a == q * 5 + r
        assert 0 <= r < 5
        print(f"a={a}, q={q}, r={r}")

    print("[유클리드 호제법]")
    a, b = 252, 105
    while b != 0:
        r = a % b
        print(f"{a} % {b} = {r}")
        a, b = b, r
    print(f"최대공약수: {gcd(252, 105)}")

    gcd_cases = [(252, 105), (-18, 30), (0, 9), (0, 0), (8, 15)]
    for a, b in gcd_cases:
        assert gcd(a, b) == standard_gcd(a, b)
    print(f"gcd 표준 함수 비교: {len(gcd_cases)}개 통과")

    for m in range(1, 8):
        for a in range(-5, 6):
            for b in range(-5, 6):
                assert (a + b) % m == ((a % m) + (b % m)) % m
                assert (a - b) % m == ((a % m) - (b % m)) % m
                assert (a * b) % m == ((a % m) * (b % m)) % m
    print("덧셈·뺄셈·곱셈 나머지 검사: 통과")

    print("[거듭제곱의 나머지]")
    power_cases = [(7, 13, 11), (3, 8, 10), (-4, 5, 7), (9, 0, 1)]
    for a, e, m in power_cases:
        actual = mod_power(a, e, m)
        expected = pow(a, e, m)
        assert actual == expected
        print(f"a={a}, e={e}, m={m}: 직접={actual}, pow={expected}")

    for a in range(-5, 6):
        for e in range(9):
            for m in range(1, 10):
                assert mod_power(a, e, m) == pow(a, e, m)
    print("작은 범위 pow 비교: 891개 통과")

    print("[처리 칸과 순환]")
    jobs = [18, 26, 34]
    print(f"처리 칸: {[job % 8 for job in jobs]}")
    size, step = 10, 4
    positions = []
    position = 0
    while True:
        positions.append(position)
        position = (position + step) % size
        if position == 0:
            break
    period = size // gcd(size, step)
    assert len(positions) == period
    print(f"방문 위치: {positions}")
    print(f"돌아오는 데 필요한 이동 횟수: {period}")


if __name__ == "__main__":
    main()

줄별 해설

from math import gcd as standard_gcd는 표준 라이브러리의 최대공약수 함수를 가져오면서 이름을 바꾼다. 직접 정의할 gcd와 구별하기 위해서다. 구현에서 표준 함수를 호출해 답을 대신 구하지는 않고, 마지막 비교에만 사용한다.

def gcd(a, b) 아래 첫 줄은 부호를 제거한다. while b != 0은 나누는 수가 0이 아닐 때만 나머지를 계산하게 한다. a, b = b, a % b에서는 오른쪽 계산이 먼저 끝난 뒤 두 변수에 값이 들어간다. 따라서 이전 a와 b로 구한 나머지를 잃지 않는다. 반복이 끝나면 a에 마지막으로 0이 아니었던 수가 남는다.

def mod_power(a, e, m)에서는 먼저 함수의 지원 범위를 검사한다. raise ValueError는 값이 약속한 범위를 벗어났음을 호출한 쪽에 알리는 예외다. 입력 오류 검사는 assert와 달리 일반적인 실행에서 유지되어야 하므로 if와 raise를 사용한다.

result = 1 % m과 base = a % m은 시작값도 나머지 범위에 맞춘다. while e > 0 안의 첫 조건은 지수가 홀수인지 검사한다. 홀수일 때 필요한 곱 하나를 result에 반영한다. 이후 base를 제곱하고 e //= 2로 지수를 줄인다. e //= 2는 e = e // 2를 줄여 쓴 문장이다. e는 함수 안에서만 줄어들며 호출한 쪽의 정수 변수는 바뀌지 않는다.

main의 몫과 나머지 반복문은 양수, 나누어떨어지는 수, 음수를 하나씩 확인한다. f로 시작하는 문자열의 중괄호 안에는 출력할 값을 넣는다. 이어지는 반복문은 호제법의 중간 나머지를 출력하므로 표에 적힌 과정과 대조할 수 있다.

gcd_cases에는 두 정수를 묶은 값들을 넣었다. 이런 순서 있는 묶음을 튜플이라고 부르며, for a, b in gcd_cases는 각 묶음의 두 값을 꺼낸다. 음수, 한쪽이 0인 입력, 둘 다 0인 입력, 서로소인 입력을 포함해 일반적인 양수 사례만 검사하는 것을 피했다.

세 겹의 나머지 검사 반복문은 m을 1부터 7까지, a와 b를 -5부터 5까지 바꾸어 덧셈, 뺄셈, 곱셈의 성질을 확인한다. range의 끝값은 포함되지 않는다. 따라서 range(-5, 6)은 11개 정수를 만든다. 이 검사는 작은 범위에서 구현과 설명이 맞는지 확인하며, 모든 정수에 대한 증명을 대신하지는 않는다.

power_cases는 손으로 추적할 사례와 경계 사례를 출력한다. expected는 비교 기준인 pow의 결과다. 이후 반복문은 밑 11개, 지수 9개, 나누는 수 9개를 조합해 891개 입력을 검사한다. 밑 0과 지수 0의 조합도 이 범위에 포함된다.

처리 칸 출력의 대괄호 안 표현은 jobs의 각 값을 나머지로 바꾸어 새 리스트를 만드는 목록 내포 문법이다. 이어지는 순환 반복문은 현재 위치를 기록한 뒤 이동하고, 출발점 0으로 돌아오면 break로 끝낸다. 출발점을 두 번 기록하지 않으므로 리스트 길이가 이동 주기와 같다. 마지막 조건문은 파일을 직접 실행했을 때 main을 호출한다.

실행 결과

main.py를 저장한 디렉터리에서 다음 명령을 실행한다. 비교 검사가 모두 참이면 별도 오류 없이 아래 결과를 출력하고 종료한다.

python3 main.py

[몫과 나머지]
a=23, q=4, r=3
a=20, q=4, r=0
a=-7, q=-2, r=3
[유클리드 호제법]
252 % 105 = 42
105 % 42 = 21
42 % 21 = 0
최대공약수: 21
gcd 표준 함수 비교: 5개 통과
덧셈·뺄셈·곱셈 나머지 검사: 통과
[거듭제곱의 나머지]
a=7, e=13, m=11: 직접=2, pow=2
a=3, e=8, m=10: 직접=1, pow=1
a=-4, e=5, m=7: 직접=5, pow=5
a=9, e=0, m=1: 직접=0, pow=0
작은 범위 pow 비교: 891개 통과
[처리 칸과 순환]
처리 칸: [2, 2, 2]
방문 위치: [0, 4, 8, 2, 6]
돌아오는 데 필요한 이동 횟수: 5

실무에서 자주 틀리는 것

실수 나눗셈 뒤 정수로 바꾸어 몫을 구한다

다음 코드는 -7과 5에서 q를 -1로 만든다. int는 실수의 소수 부분을 0 방향으로 버리므로 //의 내림과 다르다. 또한 /는 실수 계산을 거쳐 큰 정수에서 정확한 자릿값을 잃을 수 있다.

a, m = -7, 5
q = int(a / m)
r = a - q * m
print(q, r)  # -1 -2

정수의 몫과 나머지가 필요하면 처음부터 정수 연산을 사용한다.

a, m = -7, 5
q, r = divmod(a, m)
print(q, r)  # -2 3

호제법에서 이전 값을 먼저 덮어쓴다

다음 코드는 a를 바꾼 뒤 a % b를 계산한다. 첫 반복부터 b % b가 되어 나머지가 0으로 사라진다. 252와 105의 최대공약수를 105라고 잘못 판단한다.

a, b = 252, 105
while b != 0:
    a = b
    b = a % b
print(a)  # 105

두 값을 동시에 대입하거나, 이전 값으로 나머지를 먼저 계산해 보관한다. 다음 코드는 21을 출력한다.

a, b = 252, 105
while b != 0:
    remainder = a % b
    a = b
    b = remainder
print(a)  # 21

나머지 계산에서 공통 인수를 무조건 지운다

보통의 정수 등식에서 익숙한 약분을 합동 관계에 그대로 적용하면 다음 반례를 놓친다. 공통 인수 2와 나누는 수 6이 서로소가 아니므로 여기서는 2를 지울 수 없다.

assert (2 * 1) % 6 == (2 * 4) % 6
# 다음 검사는 실패한다.
assert 1 % 6 == 4 % 6

원래 비교하려던 곱의 나머지를 그대로 검사한다. 입력값 자체의 나머지가 같은지는 별개의 질문으로 둔다.

m, factor = 6, 2
left, right = 1, 4
products_match = (factor * left) % m == (factor * right) % m
values_match = left % m == right % m
print(products_match, values_match)  # True False

거듭제곱의 나머지를 두 인자 pow로 계산한다

다음 코드는 결과는 맞지만 큰 거듭제곱 전체를 먼저 만든다. 지수가 커지면 최종 나머지만 필요하다는 조건을 계산에 활용하지 못한다.

a, e, m = 7, 10000, 11
answer = pow(a, e) % m
print(answer)  # 1

표준 기능을 사용하는 실무 코드에서는 세 번째 인자로 나누는 수를 전달한다. 직접 만든 구현을 이해한 뒤에는 표준 기능을 활용하는 편이 코드의 의도를 간결하게 드러낸다.

a, e, m = 7, 10000, 11
answer = pow(a, e, m)
print(answer)  # 1

한눈에 보기

정수와 나머지 문제에서 확인할 계산 규칙과 입력 조건

주제	핵심 규칙	Python 표현	확인할 조건
몫과 나머지	a = q × m + r	divmod(a, m)	m > 0이면 0 ≤ r < m
최대공약수	두 수를 b와 나머지로 교체한다	a, b = b, a % b	b가 0이면 멈춘다
합동	두 수의 차이가 m의 배수다	a % m == b % m	나눗셈과 약분은 별도 조건이 필요하다
거듭제곱의 나머지	곱할 때마다 나머지를 취한다	pow(a, e, m)	이 장의 구현은 e ≥ 0, m > 0이다
순환 이동	이동 주기는 m // gcd(m, step)이다	(position + step) % m	m > 0이고 step은 정수다

몫과 나머지의 범위는 코드의 경계 조건을 정한다. 최대공약수는 같은 분할 단위와 순환 길이를 알려 준다. 모듈러 연산은 필요한 정보가 나머지뿐일 때 중간 계산을 줄이는 근거가 된다. 결과의 범위를 맞추는 일과 입력을 고르게 배치하는 일은 구별해서 점검한다.

연습 문제

1. 나누는 수가 7일 때 -17과 17의 몫과 나머지를 예상한다. divmod로 확인하고, 각각 q × 7 + r이 원래 수와 같은지 검사한다.
2. 완성 코드의 gcd를 이용해 84와 30의 최대공약수를 구한다. 각 반복의 a, b, 나머지를 적고, 두 입력의 순서를 바꾸어도 같은 결과가 나오는지 확인한다.
3. mod_power(5, 13, 12)의 결과를 구한다. 지수가 13, 6, 3, 1일 때 반복 시작 시점의 result와 base를 기록한다. 마지막에 pow와 비교하고, 지수 -1을 전달했을 때 함수가 어떻게 동작하는지 확인한다.
4. 크기가 12인 순환 목록에서 출발점을 0으로 두고 8씩 이동한다. 방문 위치와 이동 주기를 구한다. 이어서 5씩 이동할 때 열두 위치를 모두 방문하는지 코드와 최대공약수로 각각 확인한다.

정답과 해설

몫의 내림 방향을 확인한다

-17의 몫은 -3이고 나머지는 4다. 17의 몫은 2이고 나머지는 3이다. 음수에서도 나머지 범위를 먼저 떠올리면 몫을 확인하기 쉽다. -17 = -3 × 7 + 4가 성립한다.

for a in [-17, 17]:
    q, r = divmod(a, 7)
    assert q * 7 + r == a
    assert 0 <= r < 7
    print(a, q, r)
# -17 -3 4
# 17 2 3

공약수를 보존하며 두 수를 줄인다

나머지는 차례대로 24, 6, 0이다. 최대공약수는 6이다. 입력을 바꾸면 처음에 30 % 84 = 30이라는 단계가 추가되지만, 그 뒤에는 같은 계산으로 합류한다. 최대공약수의 뜻은 입력 순서에 의존하지 않는다. 다음 코드는 완성 코드의 gcd 정의 아래에서 실행할 수 있다.

a, b = 84, 30
while b != 0:
    r = a % b
    print(a, b, r)
    a, b = b, r
assert a == 6
assert gcd(84, 30) == gcd(30, 84) == 6

제곱할 후보와 누적한 결과를 구별한다

반복 시작 시점의 값은 다음 표와 같다. 첫 반복에서 5를 result에 곱한다. base는 제곱 후 1이 되므로 남은 반복에서 result는 5를 유지한다. 아래 코드는 완성 코드의 mod_power 정의와 함께 실행한다.

5의 13제곱을 12로 나눈 나머지 계산의 반복 시작 상태

e	result	base	이번 반복의 곱셈
13	1	5	result에 5를 곱한다
6	5	1	result를 유지한다
3	5	1	result에 1을 곱한다
1	5	1	result에 1을 곱한다

assert mod_power(5, 13, 12) == pow(5, 13, 12) == 5

try:
    mod_power(5, -1, 12)
except ValueError as error:
    print(error)
# 지수는 0 이상이어야 한다

try와 except는 실행 중 발생한 예외를 받아 처리하는 구문이다. 여기서는 지원하지 않는 지수를 거절하는지 확인한다. Python의 pow는 조건에 따라 음수 지수도 처리하지만, 직접 만든 함수의 지원 범위는 음이 아닌 지수로 한정했다. 두 함수를 비교할 때도 그 범위 안에서 입력을 고른다.

방문 주기를 최대공약수로 점검한다

8씩 이동하면 방문 위치는 [0, 8, 4]이고 이동 주기는 3이다. gcd(12, 8)이 4이므로 12 // 4와 일치한다. 5씩 이동하면 최대공약수가 1이어서 이동 주기는 12다. 다음 코드는 방문 위치에 중복이 없는지도 집합으로 검사한다.

from math import gcd

for step in [8, 5]:
    positions = []
    position = 0
    while True:
        positions.append(position)
        position = (position + step) % 12
        if position == 0:
            break
    assert len(positions) == 12 // gcd(12, step)
    assert len(set(positions)) == len(positions)
    print(step, positions)
# 8 [0, 8, 4]
# 5 [0, 5, 10, 3, 8, 1, 6, 11, 4, 9, 2, 7]

같은 이동 규칙을 반복하더라도 모든 위치를 방문하는지는 이동 간격에 달려 있다. 나머지로 위치 범위를 맞추고 최대공약수로 방문 주기를 확인하면, 반복문을 작성하기 전에 기대할 결과를 정할 수 있다. 다음 장에서는 이처럼 앞선 상태에서 다음 상태를 만드는 반복 구조를 식으로 표현한다.