# Advent of Code 2020: Day 25

Day 25 is an encryption problem using modular arithmetic. I’ve given two public keys, both of which are of the form 7^{d} mod 20201227 where d is unknown. The challenge is to find each d.

## Challenge

The puzzle can be found here. I’m given two public keys, each of which are some power of seven mod 20201227. I’m asked to find each of the exponents, and then use those to find the private key. This is similar to how some forms of asymmetric encryption work.

## Solution

To start, I need to find the exponent. There are many ways to attack this kind of challenge, but I’ll start with a simple brute force since the number space is small and I don’t expect AOC to think we all bring crypto expertise.

I can calculate a^{b} mod c in Python as `pow(a, b, c)`

. So I’ll find each loop by looping until the result matches the given key:

```
card_loop = 1
while pow(7, card_loop, 20201227) != card_pub:
card_loop += 1
door_loop = 1
while pow(7, door_loop, 20201227) != door_pub:
door_loop += 1
```

Once I have those, I’m told the encryption key is either public key raised to the other’s loop count. Starting from either public key should produce the same result:

```
priv_key = pow(card_pub, door_loop, 20201227)
assert priv_key == pow(door_pub, card_loop, 20201227)
```

That’s the answer!

It solves the test input basically instantly, but takes almost two minutes to solve the puzzle input:

```
$ time python3 day25.py 25-test
Part 1: 14897079
real 0m0.046s
user 0m0.023s
sys 0m0.011s
$ time python3 day25.py 25-puz
Part 1: 3803729
real 1m42.371s
user 1m42.272s
sys 0m0.024s
```

This is slow, and I suspect there are ways to speed this up rather than taking the brute force approach. Maybe I’ll come back to that someday.

The full code is:

```
#!/usr/bin/env python3
import sys
with open(sys.argv[1], 'r') as f:
card_pub, door_pub = list(map(int, f.read().strip().split('\n')))
card_loop = 1
while pow(7, card_loop, 20201227) != card_pub:
card_loop += 1
door_loop = 1
while pow(7, door_loop, 20201227) != door_pub:
door_loop += 1
priv_key = pow(card_pub, door_loop, 20201227)
assert priv_key == pow(door_pub, card_loop, 20201227)
print(f'Part 1: {priv_key}')
```