My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
August 27th, 2017, 07: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!
alikim is offline  
 
Reply

  My Math Forum > College Math Forum > Number Theory

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 01:54 PM
Finite field question watson Abstract Algebra 5 January 11th, 2012 01:20 PM
Finite Field Haya Linear Algebra 2 December 10th, 2011 04:57 PM
Finite field problem mahaju Abstract Algebra 1 November 20th, 2010 08:26 AM
What is a finite field? Wolf Abstract Algebra 8 April 15th, 2009 07:47 PM





Copyright © 2017 My Math Forum. All rights reserved.