# Combo Breaker

`2021-01-08`

Original Prompt ## Part 1

For our final day, we’ll be cracking the Diffie–Hellman key exchange, the very foundation of the secure internet. Let’s start with the `transform`

function the prompt describes:

`def transform(subject_num: int, loop_size: int) -> int: value = 1 for _ in range(loop_size): value *= subject_num value %= 20201227 return value`

We get the public keys from our input, so our task is to figure out what number(s) multiply into those pubic keys. We start at 1 and keep feeding potential loop size into that `transform`

function until we get our card’s public key:

```
from itertools import count
card_public_key, door_public_key = self.inputcard_loop_size = next( potential_loop_size for potential_loop_size in count(start=1) if card_public_key == transform(7, potential_loop_size))
```

`itertools.count`

simply counts up. Easier than `for x in range(1, 10000...)`

for some arbitrarily large number. In any case, that gives us our card’s loop size.

Once we know that, we transform it with the door’s public key, giving us the shared secret:

`return transform(door_public_key, card_loop_size)`

That works for the example, but runs far too long for our actual program input. Let’s speed it up. Our issue lies in the `transform`

function.

There are a couple of patterns to take advantage of. Firstly, while `value`

is less than `20201227`

, the `%`

operation doesn’t do anything. So for number of loops, we’re doing `1 * 7 * 7 * 7 * 7 * ...`

. Instead of multiplying, we can save some time using an exponent: `7 ** loop_size`

will get us the same result (assuming the result is less than `20201227`

).

But what about when it’s more than `20201227`

? Turns out it just works. Wild, right? Because `Y % X`

(when `Y > X`

) has to be less than `X`

and `Y % X`

(when `Y < X`

) is `Y`

, we know that `Y % X == Y % X % X`

(for any number of modulo operations).

So given all that, we only have to `% 20201227`

once, no matter what exponent we raise `7`

to.

```
7 % 20201227 * 7 % 20201227 * 7 % 20201227
is the same as
7 * 7 * 7 % 20201227 % 20201227 % 20201227
is the same as
7 * 7 * 7 % 20201227
is the same as
7 ** 3 % 20201227
```

With that simplification in hand, we no longer even need a loop. Our whole `transform`

function is:

`def transform(subject_num: int, loop_size: int) -> int: # return subject_num ** loop_size % 20201227 # --- or return pow(subject_num, loop_size, 20201227)`

As luck would have it, Python’s build-in `pow`

function does exactly that.

With that one change, I got my puzzle answer in ~40 seconds. Tada! That’s star number 49.

But heck, it’s the last day, we can do it even faster. After profiling our solution, we see that `pow`

takes *huge* amounts of time. Getting a single exponent is pretty fast, but my final `card_loop_size`

was nearly 18 million. So we’re repeating a ton of work calculating exponents. When calculating, `7 ** 100`

, we reuse most of the work from `7 ** 99`

, but add another 7. Instead, we should save the previous result and multiply it by 7. That changes the shape of our loop, but should be familiar:

```
card_public_key, door_public_key = self.input
val = 1card_loop_size = None # to help pylancefor card_loop_size in count(start=1): val = (val * 7) % DIVISOR if val == card_public_key: break
return pow(door_public_key, card_loop_size, DIVISOR)
```

With that, my solution clocked in at just under 2 seconds. Not a bad improvement!

## Part 2

If you’ve got all 49 stars up to this point, then all that’s left is to press the button! Congrats! :tada:

Otherwise, check the previous answers and solve old puzzles until you’re ready.

## One Last Thing

If you’ve gotten this far, I just want to say that I really appreciate you playing along with me. I’ve learned a lot writing these, and I hope you learned something reading them.

If you’ve got suggestions about the writing style, puzzle approach, or just want to say hi, please get in touch. I’d love to hear from you! Some days it feels like I’m writing into the void.

Anyway, until next year!