Day 25: Combo Breaker

Pretty straightforward today (just brute-force). Merry Christmas everyone!

# Constants

SUBJECT_NUMBER = 7

# Functions

def transform(subject_number, loop_size):
    value = 1

    for _ in range(loop_size):
        value *= subject_number
        value %= 20201227

    return value

def find_loop_size(target):
    value     = 1
    loop_size = 0

    while value != target:
        value     *= SUBJECT_NUMBER
        value     %= 20201227
        loop_size += 1

    return loop_size

# Main Execution

def main():
    card_public_key = 10705932
    door_public_key = 12301431

    card_loop_size  = find_loop_size(card_public_key)
    door_loop_size  = find_loop_size(door_public_key) 
    encryption_key  = transform(card_public_key, door_loop_size)

    print(encryption_key)

if __name__ == '__main__':
    main()

Wolfram|Alpha

7^x mod 20201227 = 2084668 solve for x

followed by

3704642^32620386 mod 20201227

I'll probably go back and actually code this one up, just for completeness's sake. Shoutouts to my partner who recognized it right away as Diffie-Hellman.

#!/usr/bin/env python3

def transform(subject, loop_size):
    v = 1
    for i in range(loop_size):
        v = (v * subject) % 20201227
    return v

card_public, door_public = map(int, open('./input', 'r').read().rstrip().split('\n'))

card_loop_size = 0
card_gen_key = 1
while card_gen_key != card_public:
    card_loop_size += 1
    card_gen_key = (card_gen_key * 7) % 20201227

print(f'card loop size: {card_loop_size}')

enc_key = transform(door_public, card_loop_size)
print(f'encryption key: {enc_key}')

use std::env;
use std::io::{prelude::*, BufReader};
use std::fs::File;

const DIVISOR: usize = 20201227;
const SUBJECT: usize = 7;

fn transform(subject: usize, loop_size: usize) -> usize {
    let mut value = 1;
    for _ in 0..loop_size {
        value *= subject;
        value %= DIVISOR;
    }
    value
}

fn day25(input: &str) {
    let file = File::open(input).expect("Input file not found.");
    let reader = BufReader::new(file);

    let input: Vec<String> = match reader.lines().collect() {
        Err(err) => panic!("Unknown error reading input: {}", err),
        Ok(result) => result,
    };
    let keys = input.iter().map(|x| x.parse::<usize>().unwrap()).collect::<Vec<_>>();

    // Find secret loop sizes
    let mut loops = vec![0, 0];
    let mut value = 1;
    for loop_size in 1.. {
        value *= SUBJECT;
        value %= DIVISOR;
        if value == keys[0] { loops[0] = loop_size; }
        if value == keys[1] { loops[1] = loop_size; }
        if loops[0] != 0 && loops[1] != 0 { break; }
    }
 
    println!("Part 1: {}", transform(keys[0],loops[1])); // 9420461
    println!("Verification: {}", transform(keys[1],loops[0]));

}

fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    day25(&filename);
}