spoiler/help
the trickiest part for me was the polynomial reduction at the end.
if you get stuck there too: since the coeffs are mod 2 you just cancel out matching terms. he first trialled x as the divisor, getting us P*x so that the x^3 term in P would become x^4 and cancel out the x^4 term in C'. the result of this trial still had an x^3 term, so still not in GF(2^3), so he trialled x+1 as the divisor. he could test this by dividing the first trial result by P and that gave a result in GF(2^3)
Comments
Displaying 0 of 1 comments
Graham Sutherland / Polynomial
In response to this postspoiler/help
I think if you do the polynomial product A(x)∙B(x) to get C'(x), then interpret the coefficients of C'(x) and P(x) as bit vectors, you can do the modulo reduction as follows:
```
c = c'
while c >= 2^3:
sh = msb(c)-msb(p)
p' = p<<sh
c ^= p'
```
where msb() returns the index of the MSB.
so in his example of C'(x)=x^4+x^3+x+1 and P(x)=x^3+x+1, the steps are:
p=1011 (x^3+x+1)
c'=11011 (x^4+x^3+x+1)
c=11011
c>=2^3
sh=1
p'=10110
c=1101
c>=2^3
sh=0
p'=1011
c=110
c<2^3
thus, c=x^2+x
Likes: 0
Replies: 0
Boosts: 0