Factoring polynomials with finite field coeffcients

[rcgldr]

I'm not sure if I should post this here or in the mathematics section.

I'm trying to find a way to implement a mapping of a larger finite field such as GF(2^64) to a composite field GF((2^32)^2). Let f(x) be a primitive polynomial for GF(2^64), with 1 bit coefficients. If the coefficients of f(x) are considered as 0 and 1 values in GF(2^32), there will be 32 unique primitive polynomial factors of the form x^2 + ax + b where the coefficients are also elements of GF(2^32), that will provide isomorphic mapping from GF(2^64) to GF((2^32)^2), where map(a b) = map(a) map(b) and map(a+b) = map(a) + map(b). I only need one of the 32 factors.

The process normally involves removing repeated factors, but in this case there are none, and then finding factors for specific degree, but in this case the degree for all factors will be 2 (quadratic).

I've done web searches for this, but not having luck with a description that explains the process well enough for me to create code. Based on the articles I've seen so far, rather than a non-feasible brute for search for 32 out of 2^64 possible combinations of values, the process can be reduced to something feasible like 2^36 or so trial combinations.

 

[andrewkirk]

As I understand it, $GF(2^{64})$ and $GF((2^{32})^2)$ are just two different ways to denote the same object. So I don't understand what you mean by an isomorphism between the two. Do you mean any field automorphism of $GF(2^{64})$? Or do you perhaps mean a field isomorphism between $GF(2^{64})$ and $GF(2^{32})\times GF(2^{32})$, although in this case we'd need to impose a field structure on that cartesian product. It's not immediately obvious to me that the most obvious (to me) structure of componentwise addition and multiplication makes the cartesian product a field. But that may be a theorem of field theory that I've forgotten, because it's several years since I've done any.

 

[Mark44]

Or do you perhaps mean a field isomorphism between $GF(2^{64})$ and $GF(2^{32})\times GF(2^{32})$

That's how I interpreted the OP's notation of $GF((2^{32})^2)$; i.e., as ordered pairs.

 

[rcgldr]

$GF(2^{64})$ and $GF((2^{32})^2)$ are just two different ways to denote the same object. ...

There needs to be a mapping between the two fields in order for them to be isomorphic (see below). In this case, an element of $GF(2^{64})$, $c_{63} x^{63} + c_{62} x^{62} + c_1 x + c_0$ is mapped to an element of $GF((2^{32})^2)$, $d_1 x + d_0$, where the coefficients of $GF(2^{64})$ are single bit elements of GF(2) and the coefficients of $GF((2^{32})^2)$ are 32 bit elements of $GF(2^{32})$ . The generator for $GF(2^{64})$ is $x$ (hex 2) and the generator for $GF((2^{32})^2)$ is also $x$ (hex 100000000).

That's how I interpreted the OP's notation of $GF((2^{32})^2)$; i.e., as ordered pairs.

Here is an example of mapping $GF(2^8)$ to $GF(((2^2)^2)^2)$ for AES inversion step. There are multiple terms used for $GF(((2^2)^2)^2)$ : sub-field, composite field, extension field, tower field, ... .

https://eprint.iacr.org/2015/763.pdf

The goal is to reduce gate count in a hardware implementation. Generally, the parameters for $GF(((2^2)^2)^2)$ are chosen, then a brute force search is done for any of the 8 out of 128 possible generators of $GF(2^8)$ that will result in isomorphic mapping: map(a b) == map(a) map(b) and map(a + b) = map(a) + map(b). The mapping is done by multiplying an element by an 8 row by 8 bit matrix to map to or from $GF(((2^2)^2)^2)$. I didn't find any articles that explain how the mapping matrix is created, so I created a short pdf file here:

https://github.com/jeffareid/finite-field/blob/master/Composite Field Mapping Example.pdf

In the case of mapping $GF(2^{64})$ to $GF((2^{32})^2)$, both of which are based on primitive polynomials, parameters could be chosen for $GF((2^{32})^2)$, followed by a search for any of 64 out of a possible $2^{63}$ generators of $GF(2^{64})$ which isn't feasible (at least not on a PC). In the case where all the fields involved are based on primitive polynomials, there is an alternative as mentioned in my original post, interpreting the single bit coefficients of the $GF(2^{64})$ primitive polynomial to be elements of $GF(2^{32})$, and finding any of 32 factors of the form $x^2 + a x + b$, which should reduce the search to $2^{32}$ times some constant (16 or so) number of possibilities. I'm having trouble finding an article that explains a factoring algorithm well enough for me to be able to translate it into code. The process of eliminating duplicate factors and finding which degree of factors are possible is not needed in this case, as there are no duplicate factors and the degree of all factors is 2. If mapping from $GF(2^{64})$ to $GF((2^{16})^4)$, all of the 16 factors are unique and degree 4.

- - -It should be noted that I've only seen the alternate method mentioned in emails between professor E J Weldon Jr and myself at a time (late 1980's) when I was working in the R&D department of a backup tape drive company.

https://ee.hawaii.edu/faculty/detail.php?usr=27

I assume this method is known by finite field experts, and perhaps taught in some finite field classes, but I've been unable to find this method mentioned in any article I've been able to find at a web site, as most of the mapping articles are targeted towards AES inversion in hardware (where brute force methods to minimize gate count are used). I have verified that this alternative method works, for up to $GF(2^{32})$ to $GF((2^{16})^2)$, which can be done via brute force search for factors, but for $GF(2^{64})$ and $GF((2^{32})^2)$, I'll need a proper way to factor a polynomial with finite field coefficients, which are documented, but not clearly enough for me to write code. I'll continue my search for an article that is readable.