Add conversion from fields to binary-like strings

[tgagne]

There should be the ability to convert binary and hex strings into elements from the fields GF(2^n) and GF(2^(4n)) and vice versa.

• A field GF(2^(4n)) should accept length n hex strings of the form 0xfff... and produce the corresponding field element.
• A field GF(2^n) should accept length n binary strings of the form 0b111... and produce the corresponding field element.
• Elements of the field GF(2^(4n)) should be able to convert themselves into length n hex strings of the form 0xfff....
• Elements of the field GF(2^n) should be able to convert themselves into length n binary strings of the form 0b111....

One of the ultimate goals for adding this is to use it for conversion in cryptographic modules which involve finite fields, such as mq.SR.

[jdemeyer]

Why strings? I think it's better to deal with numbers and then convert the numbers to strings if needed.

And this is already implemented in one direction:

sage: K.<a> = GF(2^8)
sage: (a^3+1).integer_representation()
9
sage: hex((a^3+1).integer_representation())
'0x9'

[jdemeyer]

For the other direction (number -> field element), I propose to use __getitem__ for this.

[jdemeyer]

Please create a new ticket for the vector and matrix case, let's just deal with the fields here.

[malb]

Replying to jdemeyer:

Why strings? I think it's better to deal with numbers and then convert the numbers to strings if needed.

In crypto people really like to write 0xdeadbeef for a 32-bit number and so.

[malb]

Replying to jdemeyer:

For the other direction (number -> field element), I propose to use __getitem__ for this.

On which object would you __getitem__?

[jdemeyer]

Replying to malb:

Replying to jdemeyer:

Why strings? I think it's better to deal with numbers and then convert the numbers to strings if needed.

In crypto people really like to write 0xdeadbeef for a 32-bit number and so.

Sure, I believe that. I just don't think that Sage finite fields should directly deal with such strings. We already have conversion between strings and integers, so it makes much more sense to implement conversion between finite field elements and integers.

[jdemeyer]

Replying to malb:

On which object would you __getitem__?

The finite field:

sage: K.<a> = GF(2^8)
sage: K[9]
a^3 + 1
sage: K[0x9]
a^3 + 1

[nbruin]

Replying to jdemeyer:

The finite field:

sage: K.<a> = GF(2^8)
sage: K[9]
a^3 + 1
sage: K[0x9]
a^3 + 1

Uh ... what? Where does this enumeration order on K come from? I think you mean the element for which the coefficient vector with respect to the power basis on a corresponds to the bit vector corresponding to the binary representation of the index, but that requires further adaptations. Surely we'd need it to bring agreement with

sage: list(GF(2^8,name="a"))[9]
a^5 + a^4 + a^3 + a

which seems motivated by

sage: K.<a> = GF(2^8)
sage: L=list(K)
sage: M= [0] + [a^i for i in [1..255]]
sage: L==M
True

[jdemeyer]

Replying to nbruin:

Surely we'd need it to bring agreement with

sage: list(GF(2^8,name="a"))[9]
a^5 + a^4 + a^3 + a

Bringing two things in arrangement can be solved by changing either of the two things. My vote would be on changing list(GF(q, impl="givaro")) since it's implementation-dependent:

sage: list(GF(8, 'a', impl="givaro"))
[0, a, a^2, a + 1, a^2 + a, a^2 + a + 1, a^2 + 1, 1]
sage: list(GF(8, 'a', impl="ntl"))
[0, 1, a, a + 1, a^2, a^2 + 1, a^2 + a, a^2 + a + 1]

sage: list(GF(13, 'a', impl="givaro"))
[0, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1]
sage: list(GF(13, 'a', impl="modn"))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

[tgagne]

Replying to jdemeyer:

Please create a new ticket for the vector and matrix case, let's just deal with the fields here.

A ticket for that's been created at #19578.