hop-core 0.1.0

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

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 in 0..(k-1) {
            m[i][i+1] = Field::one();
        }
        // last row: negative coefficients (to match companion convention)
        for j in 0..k {
            // store as -coeffs[k-1-j] because of ordering mapping if needed;
            // We assume coeffs provided in order [a1, a2, ..., ak] with recurrence
            // F_n = a1 F_{n-1} + ... + ak F_{n-k}
            // companion last row should be [-ak, -a_{k-1}, ..., -a1] if state is [F_n, F_{n-1},...]
            let c = coeffs[j];
            // store negative c at last row, column j
            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 in 0..self.k {
            let mut acc = Field::zero();
            for j in 0..self.k {
                acc = acc.add(self.mat[i][j].mul(v[j]));
            }
            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 in 0..self.k {
            for j in 0..self.k {
                let mut acc = Field::zero();
                for t in 0..self.k {
                    acc = acc.add(self.mat[i][t].mul(other[t][j]));
                }
                res[i][j] = acc;
            }
        }
        res
    }

    pub fn mat_pow(&self, mut exp: u64) -> Mat {
        // exponentiate the matrix self.mat to power exp
        // binary exponentiation
        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 in 0..k { id[i][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 in 0..k {
        for j in 0..k {
            let mut acc = Field::zero();
            for t in 0..k { acc = acc.add(a[i][t].mul(b[t][j])); }
            res[i][j] = acc;
        }
    }
    res
}