I'm trying to use the square and multiply algorithm to compute:
x^11 mod x^4+x+1 in Z2[x], ie. in the Galois Field 2^4, GF(16)
I believe all that I need to do is divide x^4+x+1 into x^11, and the remainder will be my answer but as I work through the division I'm getting:
-x^2 + x^5
I don't know how to do all the math notation here to make it look really nice, but I'll do my best to illustrate my division:
x^8-x^5
------------
x^4 + x + 1 |x^11
-x^11 -x^9-x^8
----------------
-x^9-x^8
+x^9+x^6+x^5
-------------------
-x^2+x^5
I'm stuck here, as I can't reduce x^4 into x^2 but I still need to reduce x^5 down at least one more degree so it fits in the field (2^4). Did I make an arithmetic error somewhere or am I way off with my understanding of the square and multiply method and Galois Fields?