F_p^n serializing to bits convention

[alexander-zw]

Being able to convert field elements to bits and vice versa would be useful for some cryptographic protocols. There are already functions to generate random field elements and serialize with << and >>, but the F_p^n fields do not yet have the functions vector<unit_64> FieldT::to_words() and bool FieldT::from_words(vector<unit_64> words) as of 09/26/2020. They would be useful to provide additional ways to generate field elements, including from hashes. These functions are currently being added in a PR, but how exactly to implement them is unclear.

Two other relevant functions are static size_t ceil_size_in_bits() (formerly size_in_bits()) and static size_t floor_size_in_bits() (formerly capacity()).

There are three options for implementing to/from_words. For convenience, say that one words is four bits, and we are trying to store 2x+2 in F_9. Storing 2 in F_3 would be 0010.

• A: 0010 0010, this is two representations of 2 in F_3 concatenated together
• B: 1010, this is two representations of 2 in F_3 with leading zeros removed concatenated together, then padded with zeros on the left to fill up the word (in this case, padding is not necessary)
• C: 1000, this is 2 * 3 + 2, then padded with zeros on the left to fill up the word (in this case, padding is not necessary)

Similarly, there are two options to implement ceil/floor_size_in_bits.

• D: size(Fp^n) = n * size(Fp) = n * ceil_or_floor(log(p)) (existing implementation)
• E: size(Fp^n) = ceil_or_floor(n * log(p))

Pros and cons:

• For A, this is the simplest and fastest implementation. It also matches with how the value is stored in the object. For this reason, the current PR will temporarily use this option.
• For B, this gives a vector of with the same size as option D's ceil_size_in_bits(). It is an simpler and faster implementation than option C. It is more compact than A, especially for small p.
• For C, this gives a vector of with the same size as option E's ceil_size_in_bits(). It is the most compact option, at most twice as compact as B.
• For D, this matches the conceptual size of the actual object, ignoring zero padding.
• For E, this matches the conceptual size of the mathematical object.