Override `random_element` in code families

[David Lucas]

For now, there's only one implementation to random_elements, and it works as follows:

1. Generate a random element of the message space (which needs to be a Vector Space)
2. Multiply it by the code's generator matrix
3. Return the result

If a code family has an encoder which works without a generator matrix, (e.g. GRS codes), it could be nice to override random_element so it works without computing a generator matrix.

[Clément Pernet]

Better than overriding in special instances, I think the default behaviour should be to call an encoder with this random message. Then it's up to the encoder to use a generating matrix or not.

[Johan Rosenkilde]

Clément's suggestion makes a lot of sense. The default encoder of course needs its message space to be F^k; otherwise, the code cannot generate a random element of the message space (since this space is not "tight", e.g. for GRS codes where F[x] is the message space).

A further reaching possibility (which might have no real-life uses) is to add random_message() to Encoder. Then random_codeword in AbstractLinearCode could be:

    E = self.encoder()
    return E(E.random_message())

It would generally behave exactly like Clément's suggestion, since the default encoder must have F^k as its message space, but it would make it possible to generate random messages and codewords with any encoder.

[Johan Rosenkilde]

Of course, Clément's suggestion doesn't currently fix the problem for GRS codes since the default encoder there encodes using a generator matrix. One could imagine a future where multipoint evaluation is faster in Sage, and where it might pay off to implement GRSEvaluationVectorEncoder using that.

Using my over-engineered example, a shrewd used could avoid the generator matrix generation by using GRSEvaluationPolynomialEncoder.