Advent of Code 2020 day 25, part 1

# Number Theory ...
#
# The puzzle seems to be based on a form of cryptographic accumulator
#
# There are two numbers, a and b, and the final key that is is generated
# is of the form
#
#    7 ** ab mod 20201227
#
# The "public keys" are 7**a and 7**b
#
# Actually, the way the puzzle states it, the final key is
#  (7 ** a) ** b, but we can replace this with 7**ab

To solve, first find a and b by looking up power % prime tables:

$ perl -E 'my $x = 1; for my $n (1..20201227) { $x = $x * 7 % 20201227; say "$n: $x" }' | egrep " 10705932| 12301431"
529361: 12301431
2232839: 10705932

This shows that a is 529361 and b is 2232839

Next, we have to find 7 ** (529361 * 2232839). However, this is too large to
calculate directly, so using a result from number theory, we replace this with:

7 ** ((529361 * 2232839) % (20201227 - 1)

Perl is able to calculate this without resorting to bignums:

$ perl -E '$ans = ((529361 * 2232839) % 20201226); say $ans'
4152619

Finally, look up that value in the left-hand column of the original power % prime script:

$ perl -E 'my $x = 1; for my $n (1..20201227) { $x = $x * 7 % 20201227; say "$n: $x" }' | egrep '^4152619'
4152619: 11328376