finite field problem

[David Ash]

Another problem, this one definitely at the more senior level:

Let GF(2) and GF(2^10) be finite fields of order 2 and 2^10 respectively, with 0 being the zero and 1 the identity elements in both fields. Let x be an element of GF(2^10) satisfying x^10+x^3+1=0.

Find a polynomial p, of degree at most 9 and coefficients in GF(2), such that if y=p(x) then y, y^2, y^4, y^8, ..., y^512 form a basis of GF(2^10) considered as a vector space over GF(2).

[t...@bellefleurbooks.com]

Dear David:

To find p, my inclination is to let x = q(y) and to find the polynomial
q. This would be the first step. The second step would be to use q to
find p. The third step would be to make sure that the values of y^(2^n)
form a basis. Each of these three steps is roughly the same difficulty.

For the problem you give, you could say that r(x) = x^10+x^3+1. If you
were to allow r to be a different polynomial, you would have the same
three steps, and after the end of the first step, there might be no
solution q, or there might be a unique solution, or there might be
multiple solutions. Likewise, after the end of the second step, there
might be no solution p, or there might be a unique solution, or there
might be multiple solutions. Similarly, after the end of the third
step, there might be no solution p, or there might be a unique solution,
or there might be multiple solutions.

For a given polynomial r, if there is no solution p at the end of the
third step, then the problem is no good. If there is a solution, it is
a good problem. If the solution is unique, the problem is better. If
the solution is unique by the end of the third step but not by the end
of the second, then the problem is even better still.

For the polynomial, r, you gave, I do not know how good the problem is,
because I have not done the three steps yet. I bet it is a good
problem.

Sincerely,

Tom

On 2021-10-06 17:35, 'David Ash' via Competition Corner Participant

> --
> You received this message because you are subscribed to the Google
> Groups "Competition Corner Participant Discussion" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to
> competition-corner-partici...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/competition-corner-participant-discussion/b0b38f3a-7738-4964-8e14-78280e955dban%40googlegroups.com
> [1].
>
>
> Links:
> ------
> [1]
> https://groups.google.com/d/msgid/competition-corner-participant-discussion/b0b38f3a-7738-4964-8e14-78280e955dban%40googlegroups.com?utm_medium=email&utm_source=footer

[t...@bellefleurbooks.com]

Dear David:

My inclination was wrong. Step 1 was a waste of effort. When you skip
step 1, step 2 amounts to computing p(x) assuming that 1, x, x^2, . . .
, x^9 form a basis. There are multiple possibilities for p here, the
simplest being p(x) = x^7. Nevertheless, you still have to prove that
1, x, x^2, . . . , x^9 form a basis (step 3) which is equivalent to
proving that x^10+x^3+1 cannot be factored.

You have much the same issue (step 3) in your approach. You state that
x^9+x^7+x^6+x^3+1 is not 1, but it could be equal to 1 if
x^9+x^7+x^6+x^3 = 0, i.e., if the two polynomials, x^9+x^7+x^6+x^3 and
x^10+x^3+1 shared a common factor. In fact, they do not, but you have
to prove as much.

Proving that x^10+x^3+1 cannot be factored, or something like this, is
something to look for in the proofs submitted. It is a good problem.

Sincerely,

Tom

On 2021-10-08 12:28, 'David Ash' via Competition Corner Participant
Discussion wrote:
> The way I'm approaching this is: we look for y to be a primitive 11th
> root of unity in GF(2^10). Given that 2 is a primitive root modulo 11,
> y, y^2, y^4, ..., y^512 reduce to y, y^2, y^3, y^4, ..., y^10. Since
> the 11th cyclotomic polynomial is irreducible this will form a basis.
> In this finite field, we know that x^1023=1 (this is true of all
> nonzero elements) and so we will be done if x^93 is not 1.
> (1023=11*93).
>
> With pen and paper (not needing a computer) we can fairly easily
> compute x^93 = x^64 * x^16 * x^13 = x^9 + x^7 + x^6 + x^3 + 1, which
> we note is not 1. Note that squaring a polynomial with coefficients in
> GF(2) is very easy. So a possible solution (it won't be the only
> solution) is p(x) = x^9 + x^7 + x^6 + x^3 + 1.
>
> On Thursday, October 7, 2021 at 4:59:36 PM UTC-7

> https://groups.google.com/d/msgid/competition-corner-participant-discussion/cac45fe2-b59e-4e91-8095-7c962b977ca6n%40googlegroups.com

> [1].
>
>
> Links:
> ------
> [1]

> https://groups.google.com/d/msgid/competition-corner-participant-discussion/cac45fe2-b59e-4e91-8095-7c962b977ca6n%40googlegroups.com?utm_medium=email&utm_source=footer

[David Ash]

There are, I believe, many possibilities for p(x) that will work, but some are easier to prove than others. Yes, x^10+x^3+1 is irreducible over GF(2) and proving that is one important step. It does then follow that 1, x, x^2, ..., x^9 form a basis but unfortunately this basis is not in the form that we are asked to find a basis. If p(x)=x^7 works, we'd have to somehow prove that x^7, x^14, x^28, x^56, ..., x^3584 form a basis. I'm not sure that you've proved that. It may very well be true--I haven't worked out the details but do know that there are a significant number of polynomials p(x) that work--there is not just one unique solution. However I believe there may be other polynomials p(x) which work and which require much less rote arithmetic (computation) to prove.

[Walter Effross]

     Could someone please unsubscribe me?

     I've tried the instructions at the bottom of these e-mails, but I'm still in the loop.

     I'm still happy to talk about the project, going forward.

               Thank you!

               Walter

---

From: 'David Ash' via Competition Corner Participant Discussion <competition-corner-p...@googlegroups.com>
Sent: Friday, October 8, 2021 5:29 PM
To: Competition Corner Participant Discussion <competition-corner-p...@googlegroups.com>
Subject: Re: finite field problem

 

To view this discussion on the web visit https://groups.google.com/d/msgid/competition-corner-participant-discussion/476565e3-22c5-4c54-9750-ba91d18f47ban%40googlegroups.com.

[Istvan Lauko]

I do think it worked. You are not in the member list any more.

[David Ash]

It might be good if Walter verified this--or at least if he verifies if it did not work since he wouldn't see this if it did! I'm still seeing the total number of members as 116 which is the number it has been for a little while now.

Also if you click on 'My membership settings' you can adjust the amount of email you get from GG. If someone wants to occasionally check in on how this discussion is going but wants to minimize spam, they can adjust the settings to get less or no email when people make postings.

[Walter Effross]

     I'm still getting the messages.

     Several times, I've tried to unsubscribe by sending an e-mail to the address listed for that; each time, I get back a message saying that it's invalid because I'm not a member.

                Best regards,               

                Walter

---

From: 'David Ash' via Competition Corner Participant Discussion <competition-corner-p...@googlegroups.com>

Sent: Friday, October 8, 2021 10:53 PM

To view this discussion on the web visit https://groups.google.com/d/msgid/competition-corner-participant-discussion/b4df0fe1-3e34-403a-b9bc-61364e8e2f67n%40googlegroups.com.

[Istvan Lauko]

I did communicate with Walter. He is still a member, but now he does not receive any emails.

I wander, if we should do this as a default for all, who are not active here (would hate to generate unwanted emails for anyone). Unfortunately there is no option for weekly or monthly "digest", only daily.

[Istvan Lauko]

I mean I wonder....  (a case in point)

[t...@bellefleurbooks.com]

Dear David:

I proved that p(x) can equal x^7, but I did not provide the proof. You
know how to do it.

By the way, every solution, p(x), has an x^7 term. I can prove this too
but have not provided the proof.

The original problem is a good problem--a little more challenging than
the Sierpinski tower.

Sincerely,

Tom

On 2021-10-08 16:29, 'David Ash' via Competition Corner Participant

> https://groups.google.com/d/msgid/competition-corner-participant-discussion/476565e3-22c5-4c54-9750-ba91d18f47ban%40googlegroups.com

> [1].
>
>
> Links:
> ------
> [1]

> https://groups.google.com/d/msgid/competition-corner-participant-discussion/476565e3-22c5-4c54-9750-ba91d18f47ban%40googlegroups.com?utm_medium=email&utm_source=footer

[David Ash]

Tom,

Yes--it appears to be true that every solution must have a (nonzero) x^7 term. To see this, first observe that it is fairly easy to show that for any element t in GF(2^10), t^1024=t. So if we repeatedly square any element of the field, we eventually get back to the original element. Note that the basis we are asked to construct basically involves taking an element and then squaring it nine times in succession to produce the other nine elements of the basis. Next we look at the squares of each of 1, x, x^2, ..., x^9:

square of 1 is 1

square of x is x^2

square of x^2 is x^4

square of x^3 is x^6

square of x^4 is x^8

square of x^5 is x^3+1

square of x^6 is x^5+x^2

square of x^7 is x^7+x^4

square of x^8 is x^9+x^6

square of x^9 is x^8+x^4+x

Note that the operation of squaring never introduces an x^7 term unless we already have an x^7 term to start with. Since a basis, by definition, must span the entire space, the only way a basis generated by squaring can span x^7 terms is if the initial element includes an x^7 term.

This might be a good alternative problem to the original problem BTW--instead of asking people to give an example of a p(x) that works instead ask them to prove that p(x) must include an x^7 term.