Christmas is here! For today’s puzzle, modular arithmetic makes its comeback. A good opportunity to try out using a library to do it, for once. This post is a literate Haskell program, that starts with a few imports.

{-# LANGUAGE DataKinds #-}
import Data.List  (elemIndex)
import Data.Maybe (fromJust)
import Data.Modular

Today’s modulus is 20201227. Probably because -25 and -26 weren’t prime.

type N = Mod Int 20201227

Let’s implement the cryptographic protocol, to get the hang of it.

A device has a secret key called “loop size”. This loop size is the parameter to a transformation function, which in effect is a power function.

newtype LoopSize = LoopSize N
transform :: N -> LoopSize -> N
transform subject (LoopSize secret) = subject^(unMod secret)

This secret can be used to generate a public key, by applying the tranformation to number 7.

newtype PublicKey = PublicKey N
mkPubKey :: LoopSize -> PublicKey
mkPubKey = PublicKey . transform 7

The encryption key to use between card and door is then defined by transforming one device’s public key with the other’s loop size. By mathematical magic¹, it happens to produce the same result. Assuming I’m the card, I’d compute it by using my secret loop size of 8 to transform the door’s public key of 17807724.

encryptionKey :: LoopSize -> PublicKey -> N
encryptionKey ls (PublicKey pk) = transform pk ls

λ> encryptionKey (LoopSize 8) (PublicKey 17807724)
14897079

Let’s verify the other party agrees.

λ> encryptionKey (LoopSize 11) (PublicKey 5764801)
14897079

All good.

Oh, but my input’s public keys aren’t the same. How do I extract the loop size from a public key?

All that needs to be done is invert the operation: public key = 7^loop size ⇔ loop size = log₇(public key)

crackLoopSize :: PublicKey -> LoopSize
crackLoopSize (PublicKey pk) = LoopSize (logarithm 7 pk)

There are a few beautiful algorithms to perform this. Considering the small modulus we have here, I’ll use worthy old brute force.

logarithm :: N -> N -> N
logarithm base power =
  toMod $ fromJust $ elemIndex power $ iterate (* base) 1

Here’s my wrapper, that also verifies the results are consistent.

main :: IO ()
main = do
  [cardPublicKey,doorPublicKey]
    <- map (PublicKey . read) . lines <$> readFile "day25.in"
  print $ encryptionKey (crackLoopSize cardPublicKey) doorPublicKey
  print $ encryptionKey (crackLoopSize doorPublicKey) cardPublicKey

This concludes today’s solution. See you soon!²