Finite fields made easy

Solutions to some typical exam questions. See my other videos
/ @randellheyman .

[@WAMProducties]

Great video! I'm trying to understand this stuff off wikipedia and all I'm doing is frying my brain. This really helped, thanks!

[@yashmandaviya1356]

What a video , i appreciate your work

[@xxxpirlo]

this make much more sense to me than the b*llshit of the book XD

[@PETAJOULE543]

Great video explaining field construction for simple cases and also for complex cases which utilize polynomials instead (method2 with alpha is little different than from own source). Also good note that number of elements of finite field must be related to prime or its powers.

[@romywilliamson4981]

Thank you!!! I have a Galois theory exam in 2 weeks and loads of the exam questions involve finite fields but no one ever taught us what they are. For ages I've been looking for a nice intuitive explanation with concrete examples, this is perfect.

[@RandellHeyman]

Thanks. I never studied Galois theory at University. On my list to do sometime.

[@romywilliamson4981]

@@RandellHeyman It's a pretty cool subject, I recommend this Galois Theory playlist that I have been using for revision kzbin.info/www/bejne/mWepnaOlp8mZes0&ab_channel=RichardE.BORCHERDSRichardE.BORCHERDS

[@Grassmpl]

In fact finite fields are indeed prefect as well as characteristic 0 fields. Why are you tested on finite fields if you didn't learn them?

[@thenapoler1881]

Thank you for this video, really helped me understand fields better.

[@LokeshSharmaa]

Awesome. Thanks

[@frantisekspurny9019]

Amazing video. You totally saved me.

[@RandellHeyman]

Glad I was able to help :)

[@johnryde6697]

Really clear. Thank you.

[@vaishnavj2589]

Great video. Thanks

[@RandellHeyman]

Glad you liked it!

[@adityamanimishra5053]

Awesome video,great work!

[@RandellHeyman]

Thanks. More videos at kzbin.info

[@adityamanimishra5053]

Randell Heyman sure

[@Grassmpl]

I immediately know the answer and this is not the video for me but I'm watching it anyways.

[@NassosKranidiotis]

Thank you so much for the excellent video!

[@ankitb3954]

Life Saver. Beautiful Video

[@RandellHeyman]

Great.

[@wingwingxd61]

Thanks!!!

[@vaishnavj2589]

Should the polynomial we are dividing be irreducible or primitive?

[@RandellHeyman]

Irreducible

[@RandellHeyman]

Thanks

[@pavankat]

Love the video! I'm trying to understand how you come up with the 9 polynomials at 2:52 from F sub 9?

[@pavankat]

is the polynomial ax+b where x=3, a and b range from 0 to 2? Is that the only way you can represent the numbers 0...8?

[@RandellHeyman]

All the polynomials ax+b where a and b can be 0,1, or 2 with all the modulo arithmetic rules that I discuss. The important point is that the field does not contain numbers. It contains polynomials.

[@pavankat]

thank you Randell!

[@praveendvd1]

@@RandellHeyman so if pollynomials are in the form of ax+b , thne how can it have higher order polynomials in it.

[@praveendvd1]

@@RandellHeyman kzbin.info/www/bejne/aZ60ZIeapN98i7M like in this video

[@ManuelBTC21]

It would have been better to be explicit at 2:50 0x + 0 1x + 0 2x + 0 0x + 1 1x + 1 2x + 1 0x + 2 1x + 2 2x + 2

[@RandellHeyman]

Manuel Barkhau Yes. I think that would have been better.

[@ruthporter8971]

How does 2(x^2 + 1) + 2 == 2?

[@pavankat]

why did you do mod3 instead of mod9 at 3:59. Is it always the base prime (3 for 27, 5 for 125) for a finite field of an order of a prime power?

[@RandellHeyman]

Pavan Katepalli yes. Always the base power as you call it.

[@pavankat]

thank you Randell! What's the proper terminology for base power/prime?

[@RandellHeyman]

There is no obvious terminology other than saying `the prime in the prime power' or similar.

[@oborooizamisi1894]

Hello, please I am still confused on how you are doing the modular reduction in g(x) after multiplication? Then how do we add and multiply: 7 and 8 for example

[@RandellHeyman]

Hi, have a look at my video Modular arithmetic made easy and then return to this video.

[@kagayakuangel5828]

Question, for this contradiction, at 5:37 when you say it is impossible for a^2d^2 = 2 you simply mean that it is impossible to find 2 numbers in the set {0, 1, 2} such that their squares can multiply to 2 right? like 0^2 • 0^2 = 0 ≠ 2 0^2 • 1^2 = 0 ≠ 2 0^2 • 2^2 = 0 ≠ 2 1^2 • 1^2 = 1 ≠ 2 1^2 • 2^2 = 4 ≡ 1 ≠ 2 (got lazy here not writing the rest of this out) ⋮ and so on...

[@RandellHeyman]

Yes. That's correct.

[@lexa-nr9vc]

все понятно, спасибо

[@Post1690]

You say a number must be invertible to be in the set, but is there any case where 0 has an inverse, where 0*x = 1?

[@RandellHeyman]

David Nemati For any field, finite or otherwise, all elements, except the element zero, must be invertible under multiplication. I don't think zero can ever have an inverse since zero is defined such that zero multiplied by any number gives zero.

[@butttasdtics]

At 5:52 how does 2x^2 + 1 = 2(x^2 + 1) + 2? I feel like there's a step missing or something I'm just not seeing.

[@RandellHeyman]

This line involves two concepts. Firstly, all coefficients (whether constants or coefficients of x or x^2) are added and multiplied modulo 3. So in this field 2+2=4=1 mod 3. Secondly, all addition and multiplication is carried out modulo x^2+1. So in this case we have 2x^2+1 and we want the remainder when divide by x^2+1. From my calculations, using both concepts, we see that the remainder is 2. Hope that helps.

[@clamato422]

i can see how 2(x^2 + 1) + 2 == 2 but, as butttasdtics originally asked: how does 2x^2 + 1 == 2(x^2 + 1) + 2 ??

[@RandellHeyman]

2(x^2+1)+2 = (2x^2+2)+2=2x^2+(2+2)=2x^2+4. But in this field the only numbers are 0,1,2,3 and multiplication and addition are carried out modulo 3. In this case 2+2 is congruent to 1 modulo 3. So the final answer is 2x^2+1. If you don't get how 2+2=1 see my video Modular arithmetic made easy. Hope that helps.

[@ManuelBTC21]

The only numbers are {0, 1, 2} not {0, 1, 2, 3}. Besides that, I'm pretty sure I'm not having a problem with Modular arithmetic, the issue is that steps are being left out. I'm learning this from scratch because I need to implement it, so highlighting the polynomial division would have been very helpful. (2x + 1) * (1x + 1) = 2x² + 2x + 1x + 1 = 2x² + 3x + 1 = 2x² + (3 % 3)x + 1 = 2x² + 0x + 1 = 2x² + 1 = (2x² + 1) % (x² + 1) At this point we need to look up polynomial division. = (2x² + 0x + 1) / (x² + 0x + 1) = 2 remainder -1 (2x² + 0x + 1) # our term - 2x² + 0x + 2 # 2 times our irreducible In other words: 2 * (x² + 1) = 2x² + 2 and (2x² + 1) - (2x² + 2) = 0x² - 1 = - 1 % 3 = 2

[@SimonePerriello]

@@ManuelBTC21 In fact, the division algorithm is not needed. Taking the irreducible polynomial x^2 + 1, you can directly apply the equality x^2 = -1 to obtain the same result. So, 2x^2 + 1 = 2 * (-1) + 1 = -1 = 2 (mod 3). But obviously the result is the same.

[@thulasiraju7713]

Sir this is this number theory topic please reply me sir

[@RandellHeyman]

From Wikipedia...Finite fields are fundamental in a number of areas of mathematics and computer science, including number theory, algebraic geometry, Galois theory,...and coding theory.

[@thulasiraju7713]

@@RandellHeyman thank you very much sir 🙏🙏

[@JohnDoe-sc4zf]

Hey, can you explain why Z2 = {0,1} with addition and multiplication modulo 2 is a field? Since, I believe 1 is the multiplicative identity, but multiplicative inverse of 0 does not exists i.e 0 * ? = 1. Then how can z2 be a field. Btw awesome video.

[@RandellHeyman]

Hi John, glad you found the video useful. The multiplicative inverse requirement for a field is that every element EXCEPT FOR THE ZERO ELEMENT has an inverse.

[@Grassmpl]

In any non-trivial commutative ring with 1, 0 can't have an inverse. Suppose a is the inverse of 0. 0=0a=1. For any element b in the ring 0b=0, so b = a0b = 0, so the ring has to be trivial.

[@Hyper7Justin]

What is the point using alpha?

[@RandellHeyman]

There are two perfectly valid, often used ways of describing a finite field where the number of elements is a prime power and that's what I show.

[@praveendvd1]

so does this mean that degree of ' i 'will always be 2 or less ?

[@RandellHeyman]

Sorry. I don't understand your question.

[@praveendvd1]

@@RandellHeyman let P be my base, so elements of Zp[x] is 0,1.....p-1, x,2x,...(p-1)x,...(p-1)x+p-1. what degree of irreducible polynomial could I choose as i(x)

[@praveendvd1]

Discuss how a finite field with p^K elements where p is a prime is constructed around Z/ p. ? i wanted to answer this question . but i am feeling it hard to answer

[@jupytr1]

Is taking mod 3 then mod x^2+1 the same as taking mod x^2+1 then mod 3 ?

[@RandellHeyman]

+David Caywood I think the answer is yes. Here's a proof for a cubic that is easier to show here It can be extended to all polynomials. Suppose we have ax^3+bx^2+cx+d, with a not equal to 0 mod 3. Calculating the polynomial mod x^2+1 we get gx+h where ax^3+bx^2+cx+d=(ex+f)(x^2+1)+gx+h. Then applying mod 3 we get g (mod 3) +h (mod 3). Now think about applying mod 3 first. Taking mod 3 of the equation above gives us g (mod 3) +h (mod 3) as the result from mod 3 then mod x^2+1. Good question....hope my answer helps.

[@willsharp9809]

Can alpha^2 + 1 be simplified to 0 because alpha is the imaginary number i?

[@RandellHeyman]

That is one way to think about it. Often we would say that alpha is a root of x^2+1. This is better if you can't/don't know what the root is. For example, for another problem we might say that alpha is the root of x^5+x^4+x^3+x^2+1.

[@Aitchdeee]

At 2:38, how does the fact that 9 = 3^2 let us produce the 9 polynomials?

[@RandellHeyman]

I've uploaded a video to explain.

[@Aitchdeee]

@@RandellHeyman Thank you

[@user-nc5fi8oi9y]

Why is 4a^2+6a+2=a^2+2 ? (8:12) Thank you for the great video!!

[@RandellHeyman]

Hi Hans. A finite field requires that in any addition or multiplication the result is an element of the field. We achieve this in 2 ways. Firstly, the coefficients are `simplified' modulo 3. So 6a is not in the field but 6 is the same as zero modulo 3. So we can replace 6a with 0a which is zero. Note that zero is an element of the field. This rule works well for addition but for multiplication we need an additional rule. We note that a^2+1=0 since a is a root of x^2+1. So we can replace any a^2+1 with zero. Combining these 2 rules you should be able to follow what I have done.

[@user-nc5fi8oi9y]

Well thanks very much!!

[@user-nc5fi8oi9y]

Umm have one more to ask.. i how can we assume a^2+1 is zero in modulo 3 cuz it’s a root of x^2+1?

[@ruthporter8971]

How does 2x^2 +1 = 2(x^2+1) +2 at 5:55

[@RandellHeyman]

I explain in the video around 3-4 min mark. If you are still unsure watch my video Modular arithmetic made easy first and then return to this video. Hope that helps.

[@ManuelBTC21]

It does not help.

[@RandellHeyman]

Ok. If you look at the right hand side of your equation you have 2(x^2+1)+2. If you expand you get 2x^2+2+2=2x^2+4. Now in this finite field all coefficients are expressed modulo 3. So if you see a 4 you change 4 to the remainder when you divide 4 by 3. Since 4=1(3)+1 the remainder when divide 4 by 3 is 1. So we replace 4 by 1. So the final answer is 2x^2+1.

[@gilian2587]

Determining which irreducible polynomial is associated with your generic GF(p^n) is the piece that I don't quite understand. GF(2^8) provides an irreducible polynomial equivalent to the hexadecimal value of 0x11B; I know this, that's what I've read; but I have no clue why, or how to derive that result for myself. Calculating result of multiplying (0x32).(0x62) on the Finite Field by hand seems to be a carpal tunnel inducing exercise; and you need to do perform this multiplication around 320 times for the AES algorithm to encrypt just one 16 Byte string. This whole thing makes me suspect that my brain might be leaking out of my left ear...

[@RandellHeyman]

Hi Gilian, Let's talk about different finite field first. Nott sure if you have come across the term isomorphic. Are you aware that all finite fields of a given number of elements are isomorphic. They are same if we are allowed to relable elements. So for many purposes it doesn't make any difference which irreducible polynomial you use. A separate problem is finding irreducible polynomials of large degree. Happy to make a video on either of these issues if you want.

[@gilian2587]

@@RandellHeyman "Nott sure if you have come across the term isomorphic." -- Iso-morphic - 'Same Form' - If I understand correctly; two structures of the same type can be reversed by an inverse mapping. Perhaps this implies commuttivity A + B = C. And this also implies that A = C - B. It may also imply that: X . Y = Z * mod(255); and Y = Z * mod(255)/ X; as long as the result of the operation generates a member of the original set; you should be in decent shape. I admit to being weak in number theory; you can see the lack of rigor in my response. -- Please feel free to correct me if my statements here are in error. "Happy to make a video on either of these issues if you want." -- I would be more than happy to watch a video on either or both issues if you feel so inclined to make either one; this has proven to be a difficult topic for me to fully comprehend; so... my response is to continue beating my head against the subject until I make some progress.

[@gilian2587]

@@RandellHeyman Actually... to be perfectly honest; I had been reading through the AES algorithm and was wanting to perform some paper calculations to form an intuition for it's behaviors; problem is... a number set with 256 valid candidates seems to be too big to develop a reasonable intuition. If I could reformulate the algorithm to use a 2x2 matrix of bytes instead of a 4x4 matrix of bytes used by AES; then, I think the process of evaluating multiplicative expressions by hand would be a little less... painful (not that one would want to actually employ it's use in that form, the whole purpose would be to help build a person's intuition). As it stands, without the smaller matrix; I think I may need to take an open source version of the algorithm and split each of the components [ 'AddRoundKey', 'SubBytes', 'ShiftRows', 'MixColumns' ] into their own standalone programs with extensive logging peppered in them. Found an interesting paper on the subject... 1) web.archive.org/web/20070203204845/csrc.nist.gov/CryptoToolkit/aes/rijndael/Rijndael.pdf 2) www.geeksforgeeks.org/modulo-2-binary-division/ (not relevant to this discussion but I'd like to refer back to it)

[@RandellHeyman]

I have uploaded a video on how to work out which irreducible polynomial is used to create the multiplication table. If your problem is how to do arithmetic in the field (eg multi, addn, inverse) let me know and I'll do another video.

[@RandellHeyman]

Hi again, I had a look at some info on AES. I see what you are trying to do. You should be able to do something by hand on a smaller finite field as you said.

[@vaishali8898]

for 7 elements how does 2 have an inverse?

[@RandellHeyman]

lol 2 times 4 = 8. But in the finite field with 7 elements all multiplication is carried out modulo 7. So 8 becomes 1. This means that 2 x 4 =1. So the inverse of 2 is 4.

[@ruthporter8971]

Inverse of 2 is a half tho?

[@ruthporter8971]

Wait I got it!

[@knox19]

I'm trying to create a 27 element field (3^3). So, the elements have coeffieicents and powers (0-2), e.g. x^2 +2, but I'm having trouble finding a primitive element to the set. Would any irreducible polynomial of power 3 work to close the field under multiplication? Do I have to use a mod 3 polynomial?

[@RandellHeyman]

Knoxort As I show in the video you need an irreducible quadratic polynomial. g (x)=x^2+2 won't work because g (1)=0 in mod 3. Use trial and error; there must be at least 1 irreducible quadratic.

[@knox19]

Understood. Thanks a lot, Randell!

[@willnewman9783]

@@RandellHeyman no, I am pretty sure he needs a cubic polynomial

[@smashingdots]

So at 4:30, how is (2x+1)(x+1)=2x^2 + 1 ???? What happens to the 3x?

[@smashingdots]

Oh I get it, because we are working modulo 3, then 3x = 0 You need to spell these things out for people: write it up, say the words, then cross through the 3x, otherwise it takes me another age of research to realize what the heck is going on. Being a good teacher is not showing how smart you are, but understanding, preempting and responding to how dopey we, the students, are :)

[@RandellHeyman]

We add ans multiply coefficients modulo 3. So 2x+x=3x=0x=0.

[@RandellHeyman]

Fair point. I can't do a cross through the 3x but I have added an annotation saying 2x+x=3x=0x=0. Thanks for the suggestion.

[@pavankat]

at 5:22 you used x^2 + 1 because it's irreducible, but how did you know to choose that particular polynomial?

[@RandellHeyman]

As I say in the video you need to pick a degree 2 polynomial of degree 2 that is irreducible in Z_3[x]. I then show why the polynomial I chose satisfies these conditions. In other situations you might have to use trial and error to find a suitable polynomial. It has been proven that there will always be at least one suitable polynomial to be found. Hope that helps.

[@pavankat]

Thank you Randell!

[@HansFlamme]

Why is 2x^2 + 1 mod (x^2+1) = 2? I get - 1 and not 2 at 5:55

[@RandellHeyman]

-1 is the same as 2 in the mod 3 world. Also see my 2nd comment to Ruth 1 year ago.

[@HansFlamme]

@@RandellHeyman how is that? I know - 1 is not in our set, that's clear to me, but how is it 2?

[@Meatchop]

why is a^2 + 1 = 0

[@RandellHeyman]

That's what it means for a to be root of the equation f(x)=x^2+1.

[@Meatchop]

ahh ok, ty

[@phazei]

Really would like a better explanation of 6:15.... 2x^2 = 2x^2 + 0 = 2x^2 + 3 = 2x^2 + 2 + 1 = 2(x^2 + 1) + 1. x^2+1⟌2x^2 + 2 + 1 = 2 + 1/(x^2 + 1) I don't understand the division...

[@RandellHeyman]

I don't understand why you are dividing. I was just showing that the inverse of x is 2x. To prove that, I multiply x by 2x and get 1.

[@phazei]

@@RandellHeyman 2x * x = 2x^2. I don't see how that becomes 1. I thought you were moding it by the irreducible. How else is it converted? I spent 4 hours googling and found nothing

[@RandellHeyman]

@@phazei Sorry to hear you've spent some much time on this. There are two rules. Firstly, the coefficients are modulo 3. E.g. 2+1=0, 2+2=1. Next polynomials are modulo x^2+1. That is the remainder when we divide by x^2+1. E.g. x^2+2=1(x^2+1)+1=1, x^3+x=x(x^2+1)+0=0. So now we can proceed. Firstly, x(2x)=2x^2 just as it did in high school. Next we have to find the remainder when we divide by x^2+1. We have (remember 3=0): 2x^2=2x^2+0=2x^2+3=2(x^2+1)+1=1. So x(2x^2)=1 and therefore the inverse of x is 2x.

[@phazei]

@@RandellHeyman Ah ha! I get that 0 = 3 since it's modulo 3, but what wasn't directly clear was that x^2+1 = 0 as well so I wasn't seeing that as a replacement when I got to 2(x^2+1) + 1 = 2(0) + 1 = 1. Thank you, I think that clears it up

[@clayrab]

Why not just say the field for answer 3 simply be 0, 1, 2, i, i+1, i+2, 2i, 2i+1, 2i+2? why complicate it by thinking about polynomials and using an abstract "root of x^2 + 1" called alpha rather than an actual root and then we just do some modulo in the complex plane and it all seems much simpler to me...

[@RandellHeyman]

That's fine for this question. But for harder problems/larger polynomials you won't know the root.

[@mark_tilltill6664]

You still have a problem with addition, Believe it or not.

[@jeffersonsteelflex8015]

Thanks!

[@RandellHeyman]

:)