0

I am looking for a fast way to compute power of matrix A in galois field 2 (GF(2)). A is a double matrix and its exponentiation of x denoted by

A^x = A * A * A * ... * A     (x times)

The simple way is that converts A to GF(2) (because given matrix A is double matrix) and then peform exponentiation operation. Matlab code

A1 = gf(A, 2) % // convert to galois field
A_pow_x_first = A1^x; % // Perform A^x

However, this way takes long time to converts matrix A to GF(2). I am looking for a fast way without GF(2) converting. That is, I using mod operation

A_pow_x_second = mod(A^x, 2)

However, the problem is that the result of first way and second way are not similar. The problem is that overflow of number. Some member suggested to me convert matrix A to int64. However, I think it is not good way to handle with my problem. Could you suggest to me a fast way to do it in matlab? Thanks in advance

This is simple example

>> A = [1     0     1
        0     1     1
        1     1     1]

First way,

>> A_pow_x_first = gf(A, 2)^50

Result:

 0           1           0
 1           0           0
 0           0           1

Second way

>> A_pow_x_second = mod(A^50, 2)

A_pow_x_second =

     0     0     0
     0     0     0
     0     0     0

How to fast compute A^x without convert to GF(2) that has similar result in first way?

mehmet
  • 1,631
  • 16
  • 21
John
  • 2,838
  • 7
  • 36
  • 65
  • possible duplicate of [Matrix Exponentiation in Galois Field 2](http://stackoverflow.com/questions/27896346/matrix-exponentiation-in-galois-field-2) – knedlsepp Jan 12 '15 at 12:40
  • 2
    Also: As you keep asking about [this paper](http://www.csd.uwo.ca/~moreno/CS424/Ressources/WIEDEMANN-IEEE-1986.pdf): Instead of computing `(A^i)*b`, you should instead compute `A*(A*(..*(A*b)))` [mod 2] using a `for` loop! And of course for computing `(A^(i+1))*b)` you should reuse the result of the previous computation `A*(A^i)*b`. – knedlsepp Jan 12 '15 at 12:48
  • 3
    The problem you are having is not an overflow, it is the limited precision of the `double` data type. MATLAB (and IEEE 754) use 52 bits for the fraction and 11 bits for the exponent. With 52 bits for the fraction, you will get a precision of about 16 digits in the decimal system. This is never enough for the values you are having. – hbaderts Jan 12 '15 at 12:50
  • @knedlsepp: yes, In this topic, I just find the problem and I found this problem is overflow problem. And I make a new topic now to resolve it. In the topic, I also find a fast way to compute power of matrix that avoid overflow of number – John Jan 12 '15 at 13:40
  • @knedlsepp: What sentence said about my problem in that paper. It is truly problem that I am resolving for that paper. Thank you in advance. – John Jan 12 '15 at 13:44
  • @hbaderts: Good point. Do you suggest to me some fast way to resolve my problem. Let refer the topic to get more detail http://stackoverflow.com/questions/27896346/matrix-exponentiation-in-galois-field-2?noredirect=1#comment44202131_27896346 – John Jan 12 '15 at 13:45
  • @user8264: You mind joining me in the [chat](http://chat.stackoverflow.com/rooms/68657/linear-systems-over-finite-field)? – knedlsepp Jan 12 '15 at 13:56

0 Answers0