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
LoopSize secret) = subject^(unMod secret) transform subject (
```

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

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

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^{1}, 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
PublicKey pk) = transform pk ls encryptionKey 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: *p**u**b**l**i**c* *k**e**y* = 7^{loop size} ⇔ *l**o**o**p* *s**i**z**e* = *l**o**g*_{7}(*p**u**b**l**i**c* *k**e**y*)

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

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 $ fromJust $ elemIndex power $ iterate (* base) 1 toMod
```

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

```
main :: IO ()
= do
main
[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!^{2}