AoC 2020 D25: Combo Breaker

| Problem statement | Source code | Tags: Brute forceModular arithmetic

← Previous Back to AoC Index

I thought there would be some neat mathematical trick to this problem exploiting the weakness of the transformation function, but it seems that brute force works just fine??

loop_size = 1
num = 7
while True:
    if num == num1:
        print(pow(num2, loop_size, 20201227))
        return
    num = (num * 7) % 20201227
    loop_size += 1

(By the way, this method of using $a^m \bmod p$ and $a^n \bmod p$ as public keys and $a^{mn} \bmod p$ as the shared secret is the Diffie–Hellman key exchange.)

← Previous Back to AoC Index