Function guff_ida::cauchy_matrix [−][src]
pub fn cauchy_matrix<G>(
field: &G,
key: &Vec<G::E>,
k: usize,
n: usize
) -> Vec<G::E> where
G: GaloisField,
Expand description
Cauchy-form matrix generated from a key
k columns | 1 1 1 | | ------- ------- ... ------- | | x1 + y1 x1 + y2 x1 + yk | | | | 1 1 1 | | ------- ------- ... ------- | | x2 + y1 x2 + y2 x2 + yk | n rows | | | : : : : | | | | 1 1 1 | | ------- ------- ... ------- | | xn + y1 xn + y2 xn + yk |
All [y1 .. yk, x1 .. xn] field values must be distinct non-zero values
TODO: Check that all input values are distinct. Can put all elements on a heap and then check that no parent node has a child node equal to it. Alternatively, check the condition as we’re building the heap? That should work, too.
TODO: use a random number number generator to select k + n distinct field elements (eg, Floyd’s algorithm for shuffling/selection from an array of all field elements if the field size is small, or a modification of the heap approach above for when it’s impractical to list all the field elements)
I’ve ordered the elements with y values first since these will be reused across all rows. I will allow passing in a vector that has more x values than are required
We don’t operate on k, n to produce field values, so they can be passed in as regular types