Convolution F_2^64

use std::io::Read;

fn main() {
    let mut input = String::new();
    std::io::stdin().read_to_string(&mut input).unwrap();
    let mut values = input.split_ascii_whitespace();
    let n: usize = values.next().unwrap().parse().unwrap();
    let m: usize = values.next().unwrap().parse().unwrap();
    let a: Vec<u64> = (0..n).map(|_| values.next().unwrap().parse().unwrap()).collect();
    let b: Vec<u64> = (0..m).map(|_| values.next().unwrap().parse().unwrap()).collect();

    let mut c = vec![0_u64; n + m - 1];
    for i in 0..n {
        for j in 0..m {
            c[i + j] ^= gf_mul(a[i], b[j]);
        }
    }

    for (i, value) in c.iter().enumerate() {
        if i > 0 {
            print!(" ");
        }
        print!("{value}");
    }
}

fn gf_mul(a: u64, mut b: u64) -> u64 {
    let mut product = 0_u128;
    while b != 0 {
        let shift = b.trailing_zeros();
        product ^= (a as u128) << shift;
        b &= b - 1;
    }
    gf_reduce(product)
}

fn gf_reduce(product: u128) -> u64 {
    let low = product as u64;
    let high = (product >> 64) as u64;
    let mut reduced = low ^ high ^ (high << 1) ^ (high << 3) ^ (high << 4);
    let carry = (high >> 63) ^ (high >> 61) ^ (high >> 60);
    reduced ^= carry ^ (carry << 1) ^ (carry << 3) ^ (carry << 4);
    reduced
}