1
$\begingroup$

Frank Luebeck's database of Conway Polynomials seems to be missing an entry for the 256-bit field, $\mathbb{F}_{2^{256}}$; neither his hosted copy nor sagemath's internal copy has it.

While there have been found irreducible polynomials for this field (such as $X^{256}+X^{10}+X^5+X^2+1$ by Bill Buchanan and $X^{256}+X^{241}+X^{178}+X^{121}+1$ by Miodrag Živković), I couldn't find any source that claimed to have found the lexographically lowest such polynomial.

Has it been found? If so, what is it? If not, were there any obstacles to finding it, or was it just an issue of (lack of) interest/need? I couldn't find anything about attempts, even.

$\endgroup$

1 Answer 1

2
$\begingroup$

When I saw how low the one Buchanan found was ($X^{256} + X^{10} + \dots$), and thought about that possibly being an upper-bound (if that one happens to be primitive, then worst-case $2^{10}$ attempts isn't that big of a number), I figured I'd try brute-forcing it, just to see if I'd get anywhere. With such a small pile of numbers to search, Sagemath handles it in just a couple of seconds!

The result: $X^{256} + X^{10} + X^5 + X^2 + 1$ is the Conway Polynomial for ${GF}{({2^{256}})}$.


Appendix: code

# Tested on Sage version 10.1, CPython version 3.10.12

R.<X> = GF(2)[]

for p in R.polynomials(of_degree=256):
    if p.is_irreducible():
        print('\u0007')
        print(p)
        if p.is_primitive():
            print("Primitive.")
            break
        else:
            print("Not primitive")
    print('.', end='')

$\endgroup$
2
  • 1
    $\begingroup$ I, too, thought that going from Buchanan's polynomial downwards should be a piece of cake with suitable software. But did you check primitivity also? IIRC a Conway polynomial need to be primitive also. Brute forcing that could still be doable, as the integer factorization of $2^{256}-1$ is known. $\endgroup$ Nov 30, 2023 at 17:46
  • $\begingroup$ @JyrkiLahtonen Good catch. (Sadly, it looks like SymPy's Poly.is_primitive is not right, here; so I had to go figure out Sage.) Interestingly, the polynomial is correct, despite my originally incorrect method of finding it. $\endgroup$ Nov 30, 2023 at 20:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .