Module day25

Combo Breaker

The card loop size is found using the Baby-step giant-step algorithm. This takes only √20201227 = 4495 steps, compared to potentially up to 20201227 steps for the brute force approach.

The common encryption key is then calculated efficiently by modular exponentiation using exponentiation by squaring.

Functions

discrete_logarithm 🔒

Baby-step giant-step algorithm to compute discrete logarithm. Constants are hardcoded to this specific problem.

parse

part1

part2