## 80 Reputation

6 years, 165 days

## True is diagonal....

True is diagonal

I will again post question

Let q=28 , F = GF(28)/(t^8 + t ^4 + t^3 + t +1), square Matrix M over F (4 x 4 or 8 x 8 matrix ...)

Need to do the following tasks:

1. Compute the characteristic polynomial p(t) of the M

2. Find the factors of p(t)

3. Find the roots of these factors in the extension field of GF(q)

p(t) = (t - x1)(t-x2)...(t - xn) , where xi is the eigenvalue of M in GF(qm), where m is the maximum degree of the factor
Note:

– If a factor is of degree 1, then there is a root in GF(28), which is the constant part of the factor.
– Else the roots are 256, 256256, 256512 · · · 256256×(di−1) in GF(2(8×di))/GF(28), where di is the degree of the factor.

4. Compute eigenvectors of M and receive matrix P (each columm of P is a eigenvector corresponding to the eigenvalue xi) in GF(qm).

5. Compute P-1

6. Construct matrix diagonal D, in which D[i,i] = xand D[i,jj] = 0

7. Compute D1/k (with any k as variable)

8. Compute S = P x D1/k x P-1

## @Carl Love True is diagonal I will again...

@Carl Love

True is diagonal

I will again post question

Let q=28 , F = GF(28)/(t^8 + t ^4 + t^3 + t +1), square Matrix M over F (4 x 4 or 8 x 8 matrix ...)

Need to do the following tasks:

1. Compute the characteristic polynomial p(t) of the M

2. Find the factors of p(t)

3. Find the roots of these factors in the extension field of GF(q)

p(t) = (t - x1)(t-x2)...(t - xn) , where xi is the eigenvalue of M in GF(qm), where m is the maximum degree of the factor
Note:

– If a factor is of degree 1, then there is a root in GF(28), which is the constant part of the factor.
– Else the roots are 256, 256256, 256512 · · · 256256×(di−1) in GF(2(8×di))/GF(28), where di is the degree of the factor.

4. Compute eigenvectors of M and receive matrix P (each columm of P is a eigenvector corresponding to the eigenvalue xi) in GF(qm).

5. Compute P-1

6. Construct matrix diagonal D, in which D[i,i] = xand D[i,jj] = 0

7. Compute D1/k (with any k as variable)

8. Compute S = P x D1/k x P-1

The matrixs P, D base on matrix the given matrix M (as your answer title "Primfield")

P is matrix of the eigenvectors of M. D is Diagonalizable matrix of the eigenvalues of M

## How to compute the following matrixs in ...

The previous parts, we computed eigenvalues (x1,x2,...,xnambda_i)and eigenvectors of the given matrix.

I need to do the following tasks in extension field (Primfield) :

1. Receive matrix and it's inverse matrix of eigenvectors (denote P and P-1), diagonalizable matrix D, in wich d[i,i] = xi . These matrixs in Primfield.

2. Compute matrix B = P x D1/4 x P-1

(I think, we can select an irreducible polynomialin GF((28)2) for computing. Example: f = t2 + 467t + 1 . Degree of f is equal to degree of factor, that is of degree > 1)

## @Carl Love  Thank you very much. Tr...

Thank you very much.

True value is 231. About 255^255 = 487, may be excuted by mod  of the some irreducible polynomial

The characteristic polynomial p(x) of the matrix M can be factored using algorithm Ben-Or’s algorithm.
– If a factor is of degree 1, then there is a root in GF(2^8), which is the constant part of the factor.
– Else the roots are 256, 256^256, 256^512 · · · 256^(256×(di−1)) in GF(2^(8×di))/GF(2^8),
where di is the degree of the factor.

Accordingly, p:=  there are two roots 37 and 217 in GF*2^8). And factor  there are two roots. That are 256 and 256^256.

## @Carl Love  These are comands in ma...

These are comands in maple:

> alias(x = RootOf(y^8+y^4+y^3+y+1));

> M:=Matrix([[1, x, 1, x^2], [x^2, x^3+1, x^2+x, x^4+1], [x^4+1, x^5+x^2+x, x^4+x^3, x^6+x], [x^6+x, x^7+x^4+x^2+1, x^6+x^5+x^2, x^3+x+1]])

> p:=Charpoly(M,t) mod 2; {result p:= t^4+(x^3+x+1+x^4)*t^3+t^2+x^4*t+1. (x^4 + x^3 + x + 1) is representation of 27 in GF(2^8)/(x^8 + y^4 + y^3 +1). p(x) over GF(2^8) it's that coefficients of p(x) in GF(2^8) (coefficients in the set {0,1,...,255} }

>Factors(p, x) mod 2; {result: (t + 37)(t + 217)(t^2 + 213t +30). 37 = x^5+x^2+1 in GF(2^8) }

## @Carl Love Thank you very much. I&n...

@Carl Love

Thank you very much. I successfully implemented your code

I'm afraid to bother you again!

I have polynomial: p(x) = x^4 + 27x^3 + x^2 + 16x +1 over GF(2^8)

The factors of this polynomial are: (x + 37)(x + 217)(x^2 + 213x +30)

Hence there two roots of p(x): x = 37 and x = 217 in GF(2^8). But in extension field GF((2^8)^2), also there are two roots of factor x^2 + 213x + 30 (x = 256 and x = 256^256 = 487). How to find these roots of p(x) over extension field GF((2^8)^2) in maple?

## @Carl Love  Of course I used a...

Of course I used alias(x=RootOf(...)). But these are some errors with proc for computing Eigenvector

> alias(x= RootOf(y^8+y^4+y^3+y+1)):

M := Matrix([[0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1], [1, x, 1, x^2]]);

eig := Eigenvalues(M) mod 2;  (ok)

>Eigenvector(M, eig[1, 1]) mod 2; (no result)
Error, (in type/polynom) testing against an invalid type

## These are some errors in proc Eigenvecto...

These are some errors with proc for computing Eigenvector

> M := Matrix([[0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1], [1, x, 1, x^2]]);

eig := Eigenvalues(M) mod 2;  (ok)

>Eigenvector(M, eig[1, 1]) mod 2; (no result)
Error, (in type/polynom) testing against an invalid type

## Thank you very much @Carl Love  I e...

Thank you very much

I excuted your example with finite field (G:=GF(2,8,x^8 + x^4 +x^3 + x + 1) and matrix