[cryptohack] Successive Powers

영국의 밴드 blur의 Charmeless Man이라는 노래가 있다.
동아리 후배로부터 추천 받은 노래인데, 가사는 모르겠고 참 조타 ㅋㅋ

풀이1

이번 문제는 제목부터가, 연속적인 거듭제곱인 문제였다.
문제에서는 펜으로도 풀 수 있는 문제라고 되어있었는데 생각이 귀찮아서 코드로 풀고, 다른 풀이들을 통해 익힌 바도 풀이2에 첨부했당.

given = [588,665,216,113,642,4,836,114,851,492,819,237]

for i in range(100, 1000):
    for j in range(i):
        if((given[0]*j)%i == given[1]):
            print(i, j)
            for k in range(len(given)-1):
                if((given[k]*j)%i != given[k+1]):
                    break
            else:
                print("true")

가장 기본적인 틀은 브루트포스를 담고 있다.
그리고 정수론에서, 모듈로보다 큰 값의 곱은 그 값의 나머지 값과도 동치이기에 모듈로와 그보다 작은 값들을 이중으로 탐색했다.

문제 없이 답을 구할 수 있다.

풀이2

일단은 코드로 문제를 풀고 싶었던 이유가, 처음부터 1승, 2승이 아닌 이상, 어떠한 수($x$)의 거듭제곱인지를 생각해야하므로 굉장히 귀찮았었다.

그리고 주어진 수열을 살펴보지도 않은 것이 손으로 문제를 풀지 못하게 한 큰 원인이었다고 생각한다.

일단은 수열을 보자면, 가장 큰 힌트는 113, 642 부분과 114, 851 부분이다.

이를 수식으로 풀어보면 아래와 같다.

$113 \times x \equiv 642 \pmod p$
$114 \times x \equiv (113 + 1) \times x \equiv 851 \pmod p$

이를 통해서 $x$가 $851-642 = 209$라는 것을 알 수 있다.

그리고 이 $x$를 토대로 $p$를 구해보쟈.

$113 \times x \equiv 113 \times 209 \equiv 23617 \equiv 642 \pmod p$

$23617 - 642 \equiv 22975 \equiv 0 \pmod p$

$22975 = 5^2 \times 919$

따라서 세자리 수라는 적합한 모듈로 $p$는 919라는 것을 큰 연산 없이도 알 수 있다.