Jump to:
D1 | D2 | D3 | D4 | D5 | D6 | D7 | D8 | D9 | D10 | D11 | D12 | D13 | D14 | D15 | D16 | D17 | D18 | D19 | D20 | D21 | D22 | D23 | D24 | D25
Part 1
We've finally reached the end! If you've actually been reading along since the beginning, let me first just express my appreciation for joining me on this journey. I've definitely learned a lot (including how much I have left to learn). Let's finish up AoC 2020!
Day 25 has a cryptographic theme to it, both in flavor and in concept. We are asked to compute discrete logarithms. This is a common problem in cryptography, and the security of many systems in the world relies on the discrete logarithm problem being a hard problem (it is the basis for the Diffie-Hellman key exchange, which is used in RSA cryptography). Thankfully, the modulus we are given here is relatively small, so this problem is still crackable using conventional computers.
import D25input
import qualified Data.List as List
discreteLog :: Int -> Int -> Int -> Int
discreteLog b t p = List.length $ List.unfoldr advanceSeed 1
where advanceSeed x
| x == t = Nothing
| otherwise = let next = (x * b) `mod` p
in Just (next, next)
getNth :: Int -> Int -> Int -> Int
getNth 0 s p = 1
getNth n s p = ((getNth (n-1) s p) * s) `mod` p
solve :: Int
solve = let cardIters = discreteLog subject cardKey prime
doorIters = discreteLog subject doorKey prime
in getNth doorIters cardKey prime
main :: IO ()
main = print $ solve
Our discrete log function takes a brute force approach of trying each modular exponent of our base until we find the target remainder. It exploits unfoldr to generate the list of all modular exponents starting from exponent 0 up until the target remainder is reached, and then returns the length of that list, which will correspond to the exponent we are seeking.
getNth performs the reverse, also known as modular exponentiation. Again, we take a brute force approach, computing each exponent from the previous, making sure to take the modulo as we go to keep the numbers manageably small.
As always, the solve function puts it all together to compute the final public key. We arbitrarily choose to apply "doorIters" to the card's public key, but, as explained in the problem, we could just as easily have applied "cardIters" to the door's public key and obtained the same answer.
One final note before we wrap up 2020. More efficient methods for computing discrete logarithms exist than the linear brute force presented here. Haskell even has a package for it (although I haven't tried using it). Moreover, the modular exponentiation can also be done more efficiently. In this case, though, with a prime of only 20 million, brute force does just fine, and the compiled binary still find the answer in under one second.
Jump to:
D1 | D2 | D3 | D4 | D5 | D6 | D7 | D8 | D9 | D10 | D11 | D12 | D13 | D14 | D15 | D16 | D17 | D18 | D19 | D20 | D21 | D22 | D23 | D24 | D25