hop-core 0.1.1

HOP core — finite-field companion-matrix stream primitives (prototype)
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

// Copyright (c) 2025 Lex Luger. All Rights Reserved.
// This software (HOP-CORE) is proprietary and confidential.
// Unauthorized copying, distribution, or use is strictly prohibited
// without explicit written permission from the author.
// Commercial licenses are available. Contact: lexluger.dev@proton.me
use crate::modules::field::Field;

/// Companion matrix utilities (dense matrix representation)
/// Matrices are represented as Vec<Vec<Field>> in row-major order.
pub type Mat = Vec<Vec<Field>>;
pub type VecF = Vec<Field>;

/// Build companion matrix for polynomial: x^k + c_{k-1} x^{k-1} + ... + c_0
/// Input: coeffs = [c_0, c_1, ..., c_{k-1}] corresponding to recurrence
/// Companion here corresponds to state update for vector [F_n, F_{n-1}, ..., F_{n-k+1}]^T
pub struct CompanionMatrix {
    pub k: usize,
    pub mat: Mat,
}

impl CompanionMatrix {
    pub fn from_coeffs(coeffs: &[u64]) -> Self {
        let k = coeffs.len();
        let mut m: Mat = vec![vec![Field::zero(); k]; k];

        // superdiagonal ones
        for (i, row) in m.iter_mut().enumerate().take(k - 1) {
            row[i + 1] = Field::one();
        }

        // last row: negative coefficients
        for (j, &c) in coeffs.iter().enumerate().take(k) {
            let neg = Field::new(
                (Field::MOD as u128 - (c as u128 % Field::MOD as u128)) % (Field::MOD as u128),
            );
            m[k - 1][j] = neg;
        }

        CompanionMatrix { k, mat: m }
    }

    pub fn mat_vec_mul(&self, v: &VecF) -> VecF {
        assert_eq!(v.len(), self.k);
        let mut out = vec![Field::zero(); self.k];
        for (i, row) in self.mat.iter().enumerate() {
            let mut acc = Field::zero();
            for (val, &vj) in row.iter().zip(v.iter()) {
                acc = acc + (*val * vj);
            }
            out[i] = acc;
        }
        out
    }

    pub fn mat_mul(&self, other: &Mat) -> Mat {
        assert_eq!(other.len(), self.k);
        let mut res = vec![vec![Field::zero(); self.k]; self.k];
        for (i, row_a) in self.mat.iter().enumerate() {
            for (j, _col_b) in (0..self.k).enumerate() {
                let mut acc = Field::zero();
                for (t, &val_a) in row_a.iter().enumerate() {
                    acc = acc + (val_a * other[t][j]);
                }
                res[i][j] = acc;
            }
        }
        res
    }

    pub fn mat_pow(&self, mut exp: u64) -> Mat {
        let mut base = self.mat.clone();
        let mut res = identity(self.k);
        while exp > 0 {
            if exp & 1 == 1 {
                res = multiply_mat(&res, &base);
            }
            base = multiply_mat(&base, &base);
            exp >>= 1;
        }
        res
    }
}

pub fn identity(k: usize) -> Mat {
    let mut id = vec![vec![Field::zero(); k]; k];
    for (i, row) in id.iter_mut().enumerate().take(k) {
        row[i] = Field::one();
    }
    id
}

pub fn multiply_mat(a: &Mat, b: &Mat) -> Mat {
    let k = a.len();
    let mut res = vec![vec![Field::zero(); k]; k];
    for (i, row_a) in a.iter().enumerate().take(k) {
        for j in 0..k {
            let mut acc = Field::zero();
            for (t, &val_a) in row_a.iter().enumerate().take(k) {
                acc = acc + (val_a * b[t][j]);
            }
            res[i][j] = acc;
        }
    }
    res
}