Add conversion from fields to binary-like strings

[870a0b74-843c-423e-a737-fef34761f72a]

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.

CC: @rbeezer @malb

Component: finite rings

Keywords: finite field, hex strings, binary strings

Issue created by migration from https://trac.sagemath.org/ticket/19531

[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]

comment:2

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

[jdemeyer]

comment:3

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

[malb]

comment:4

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]

comment:5

Replying to @jdemeyer:

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

On which object would you __getitem__?

[jdemeyer]

comment:6

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]

comment:7

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]

comment:8

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]

comment:9

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]

[870a0b74-843c-423e-a737-fef34761f72a]

comment:10

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.

[870a0b74-843c-423e-a737-fef34761f72a]

Description changed:

--- 
+++ 
@@ -2,9 +2,7 @@

 - 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.
-- Matrix spaces and vector spaces over these fields should accept strings of similar form and should break up the strings accordingly to produce a matrix or vector.
 - 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...`.
-- Matrices and vectors over these finite fields should be able to combine the individual hex/binary strings for each of its elements into a single long string.

 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`.