
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
August 27th, 2017, 06:27 AM  #1 
Newbie Joined: Jun 2009 Posts: 19 Thanks: 1  Factorization and GCD for Rijndael's finite field
I'm factoring polynomials in GF(2^8) with modulo polynomial $\displaystyle m = 2^8 + 2^4 + 2^3 + 2^1 + 2^0$ In particular, I factored a = 0x49 = $\displaystyle 2^6 + 2^3 + 2^0 = 2^1 * (2^1 + 2^0)^6 * (2^2 + 2^1 + 2^0) * (2^4 + 2^1 + 2^0) * (2^3 + 2^1 + 2^0)$ (mod m) b = 0x64 = $\displaystyle (2^6 + 2^5 + 2^2) = (2^1)^3 * (2^1 + 2^0) * (2^3 + 2^1 + 2^0) * (2^3 + 2^2 + 2^0)$ (mod m) these numbers are multiplicative inverses and I can calculate directly using long division that ab(mod m) = 2^0. I assume GCD should also be 1, i.e. 2^0. Now I want to calculate GCD using just factored irreducible polynomials. I know that for integers GCD equals the product of prime numbers (including their powers) present in both factorization, does it still hold here? $\displaystyle gcd = 2^1 * (2^1 + 2^0) * (2^3 + 2^1 + 2^0)$ (mod m) = $\displaystyle 2^5 + 2^4 + 2^3 + 2^1$ Can anyone please tell me where I am mistaken? Thank you! 

Tags 
factorization, field, finite, gcd, rijndael 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Finite field  Lullaby  Abstract Algebra  4  September 23rd, 2012 12:54 PM 
Finite field question  watson  Abstract Algebra  5  January 11th, 2012 12:20 PM 
Finite Field  Haya  Linear Algebra  2  December 10th, 2011 03:57 PM 
Finite field problem  mahaju  Abstract Algebra  1  November 20th, 2010 07:26 AM 
What is a finite field?  Wolf  Abstract Algebra  8  April 15th, 2009 06:47 PM 