complete the FEC and "linear algebra" tests

• komodo::linalg::Matrix::random is tested
• komodo::linalg::Matrix::inverse is tested on more matrix sizes, from 1 to 20 random matrices
• komodo::field tests have been double-checked
• pure "recoding" tests from komodo::fec have been double-checked
• end_to_end and end_to_end_with_recoding now runs for k \in [3, 5] and \rho \in [\frac{1}{2}, \frac{1}{3}] with n = \lfloor \frac{k}{\rho} \rfloor
• all "k among n + t" combinations are tested with try_all_decoding_combinations, possibly with some removals in case recoding is involved with is_inside

Important
on my machine, make test goes from less than 8sec on latest main to around 40sec with this MR

src/fec.rs

@@ -200,7 +200,7 @@ mod tests {
     use ark_ff::PrimeField;
 
     use crate::{
-        fec::{decode, encode, Shard},
+        fec::{decode, encode, recode_random, Shard},
         field,
         linalg::Matrix,
     };
@@ -217,24 +217,28 @@ mod tests {
         F::from_le_bytes_mod_order(&n.to_le_bytes())
     }
 
-    fn is_inside(set: &[Vec<usize>], x: &[usize]) -> bool {
+    /// `contains_one_of(x, set)` is true iif `x` fully contains one of the lists from `set`
+    ///
+    /// > **Note**  
+    /// > see [`containment`] for some example
+    fn contains_one_of(x: &[usize], set: &[Vec<usize>]) -> bool {
         set.iter().any(|y| y.iter().all(|z| x.contains(z)))
     }
 
     #[test]
-    fn exclusion() {
-        assert!(is_inside(&[vec![1, 2, 3]], &[1, 2, 3]));
-        assert!(is_inside(
+    fn containment() {
+        assert!(contains_one_of(&[1, 2, 3], &[vec![1, 2, 3]]));
+        assert!(contains_one_of(
+            &[3, 6, 8],
             &[vec![2, 4, 6], vec![1, 3, 7], vec![6, 7, 8], vec![3, 6, 8]],
-            &[3, 6, 8]
         ));
-        assert!(!is_inside(
+        assert!(!contains_one_of(
+            &[1, 6, 8],
             &[vec![2, 4, 6], vec![1, 3, 7], vec![6, 7, 8], vec![3, 6, 8]],
-            &[1, 6, 8]
         ));
-        assert!(is_inside(
+        assert!(contains_one_of(
+            &[3, 6, 8, 9, 10],
             &[vec![2, 4, 6], vec![1, 3, 7], vec![6, 7, 8], vec![3, 6, 8]],
-            &[3, 6, 8, 9, 10]
         ));
     }
 
@@ -244,7 +248,7 @@ mod tests {
         k: usize,
         test_case: &str,
         limit: Option<usize>,
-        exclude: Vec<Vec<usize>>,
+        should_not_be_decodable: Vec<Vec<usize>>,
     ) {
         for c in shards
             .iter()
@@ -258,7 +262,7 @@ mod tests {
 
             let actual = decode::<F>(s);
 
-            if is_inside(&exclude, &is) {
+            if contains_one_of(&is, &should_not_be_decodable) {
                 assert!(
                     actual.is_err(),
                     "should not decode with {:?} {test_case}",
@@ -282,10 +286,10 @@ mod tests {
         let mut rng = ark_std::test_rng();
         let test_case = format!("TEST | data: {} bytes, k: {}, n: {}", data.len(), k, n);
 
-        let shards = encode::<F>(data, &Matrix::random(k, n, &mut rng));
-        assert!(shards.is_ok(), "could not encode {test_case}");
+        let shards = encode::<F>(data, &Matrix::random(k, n, &mut rng))
+            .unwrap_or_else(|_| panic!("could not encode {test_case}"));
 
-        try_all_decoding_combinations(data, &shards.unwrap(), k, &test_case, None, vec![]);
+        try_all_decoding_combinations(data, &shards, k, &test_case, None, vec![]);
     }
 
     fn end_to_end_with_recoding_template<F: PrimeField>(data: &[u8], k: usize, n: usize) {
@@ -294,24 +298,39 @@ mod tests {
         let mut rng = ark_std::test_rng();
         let test_case = format!("TEST | data: {} bytes, k: {}, n: {}", data.len(), k, n);
 
-        let shards = encode::<F>(data, &Matrix::random(k, n, &mut rng));
-        assert!(shards.is_ok(), "could not encode {test_case}");
-
-        let mut shards = shards.unwrap();
-        shards.push(shards[2].recode_with(to_curve(7), &shards[4], to_curve(6)));
-        shards.push(shards[1].recode_with(to_curve(5), &shards[3], to_curve(4)));
-
-        // n     = (2, 4)
-        // n + 1 = (1, 3)
+        let mut shards = encode::<F>(data, &Matrix::random(k, n, &mut rng))
+            .unwrap_or_else(|_| panic!("could not encode {test_case}"));
+
+        let recoding_steps = [
+            vec![2, 4],       // =  n
+            vec![1, 3],       // = (n + 1)
+            vec![n, (n + 1)], // = (n + 2) = ((2, 4), (1, 3))
+            vec![0],          // = (n + 3) = (0)
+            vec![0],          // = (n + 4) = (0)
+        ];
+        let should_not_be_decodable = vec![
+            vec![2, 4, n],
+            vec![1, 3, (n + 1)],
+            vec![n, (n + 1), (n + 2)],
+            vec![1, 3, n, (n + 2)],
+            vec![2, 4, (n + 1), (n + 2)],
+            vec![1, 2, 3, 4, (n + 2)],
+            vec![0, (n + 3)],
+            vec![0, (n + 4)],
+            vec![(n + 3), (n + 4)],
+        ];
+
+        for step in recoding_steps {
+            let shards_to_recode: Vec<_> = shards
+                .iter()
+                .cloned()
+                .enumerate()
+                .filter_map(|(i, s)| if step.contains(&i) { Some(s) } else { None })
+                .collect();
+            shards.push(recode_random(&shards_to_recode, &mut rng).unwrap().unwrap());
+        }
 
-        try_all_decoding_combinations(
-            data,
-            &shards,
-            k,
-            &test_case,
-            None,
-            vec![vec![2, 4, n], vec![1, 3, (n + 1)]],
-        );
+        try_all_decoding_combinations(data, &shards, k, &test_case, None, should_not_be_decodable);
     }
 
     #[test]