Opened 4 years ago

Last modified 4 years ago

#19531 new enhancement

Add conversion from fields to binary-like strings

Reported by: tgagne Owned by:
Priority: major Milestone: sage-6.10
Component: finite rings Keywords: finite field, hex strings, binary strings
Cc: rbeezer, malb Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by 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.

Change History (10)

comment:1 in reply to: ↑ description ; follow-up: Changed 4 years ago by 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'

comment:2 follow-up: Changed 4 years ago by jdemeyer

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

comment:3 follow-up: Changed 4 years ago by jdemeyer

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

comment:4 in reply to: ↑ 1 ; follow-up: Changed 4 years ago by 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.

comment:5 in reply to: ↑ 2 ; follow-up: Changed 4 years ago by malb

Replying to jdemeyer:

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

On which object would you __getitem__?

comment:6 in reply to: ↑ 4 Changed 4 years ago by 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.

comment:7 in reply to: ↑ 5 ; follow-up: Changed 4 years ago by 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

comment:8 in reply to: ↑ 7 ; follow-up: Changed 4 years ago by 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

comment:9 in reply to: ↑ 8 Changed 4 years ago by 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]

comment:10 in reply to: ↑ 3 Changed 4 years ago by tgagne

  • Description modified (diff)

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.

Note: See TracTickets for help on using tickets.