0

I am confusing about exponentiation of matrix in Galois Field 2. Assume that I have a matrix that is represented in Galois Field 2 (GF2). I want to take exponentiation of 30. That is,

A^30

In the matlab we have two way to do it.

First, We perform A power 30 and take mod of 2 (Note that A is a double matrix)

 A1=mod(A^30,2)

Second way, we convert A to galois matrix and take exponentiation 

A=gf(A,2)
A2=A^30

Actually, two way must same result. However, when I check A1 and A2. They have a different result. What is happen in here? Thanks Let see my A matrix

A =

     1     1     0     1     1     1     0     1     0     0     0     1     0     1     0
     0     0     0     1     0     1     0     0     0     0     0     0     0     1     0
     0     0     0     0     0     0     0     0     1     0     1     0     0     0     1
     1     0     1     1     0     0     0     0     0     0     1     1     1     0     0
     1     0     1     0     0     0     0     1     0     0     0     0     0     0     0
     0     1     0     1     1     1     1     1     0     1     1     1     1     0     1
     0     0     0     1     0     0     0     1     0     0     1     0     0     0     0
     0     0     0     0     1     0     0     0     0     0     0     0     0     0     0
     1     0     0     1     0     1     0     0     0     1     0     0     0     0     0
     0     0     0     0     0     0     0     0     0     0     1     0     0     1     1
     1     0     1     0     0     0     0     0     0     0     1     0     0     0     1
     0     1     0     0     0     0     0     1     0     0     0     0     0     0     0
     1     0     1     1     1     1     1     1     1     0     1     1     1     0     1
     0     1     0     0     0     1     0     0     0     1     0     0     0     1     0
     1     0     0     1     0     1     0     0     0     1     0     0     0     1     1

Method1:

A1=

     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0

Method 2

A2 =

     1     1     0     1     1     1     0     1     0     0     0     1     0     1     0
     0     0     0     1     0     1     0     0     0     0     0     0     0     1     0
     0     0     0     0     0     0     0     0     1     0     1     0     0     0     1
     1     0     1     1     0     0     0     0     0     0     1     1     1     0     0
     1     0     1     0     0     0     0     1     0     0     0     0     0     0     0
     0     1     0     1     1     1     1     1     0     1     1     1     1     0     1
     0     0     0     1     0     0     0     1     0     0     1     0     0     0     0
     0     0     0     0     1     0     0     0     0     0     0     0     0     0     0
     1     0     0     1     0     1     0     0     0     1     0     0     0     0     0
     0     0     0     0     0     0     0     0     0     0     1     0     0     1     1
     1     0     1     0     0     0     0     0     0     0     1     0     0     0     1
     0     1     0     0     0     0     0     1     0     0     0     0     0     0     0
     1     0     1     1     1     1     1     1     1     0     1     1     1     0     1
     0     1     0     0     0     1     0     0     0     1     0     0     0     1     0
     1     0     0     1     0     1     0     0     0     1     0     0     0     1     1
John
  • 2,838
  • 7
  • 36
  • 65
  • What's the result of `A=gf(A,2)`? – didierc Jan 12 '15 at 06:43
  • It convers A matrix (double type) to galois matrix (GF(2) – John Jan 12 '15 at 06:49
  • I meant, on your sample matrix, what is the content of `gf(A,2)`? – didierc Jan 12 '15 at 06:58
  • From what I see, A looks like it is already a GF(2). – didierc Jan 12 '15 at 07:01
  • Actually, matrix A is double type, although it has only 1 and 0. To convert number to galois field we can peform mod operations. For example, if we consider GF(2) and we have a number is 3, So 3 in GF(2) is 1 (3 mod 2). It is similar the matrix A. 1 in matrix A can be replaced by 3 or 5.... – John Jan 12 '15 at 07:07
  • 1
    @didierc: no commuting, if the OP explicitly specifies the type as GF(2), then Matlab should perform the addition/multiplication in GF(2). – Oliver Charlesworth Jan 12 '15 at 07:16
  • @user8264: why don't you try a *much* smaller matrix first, which is easier to reason about? – Oliver Charlesworth Jan 12 '15 at 07:17
  • I perform with small matrix such as A[1 0 0;0 1 1; 1 1 1], then two ways give same result. However, I increase the size of matrix A, it has wrong. I think the problem is overflow of number. – John Jan 12 '15 at 07:19
  • @user8264: yes, numeric precision is a real possibility here. You could try computing as int64. – Oliver Charlesworth Jan 12 '15 at 07:21
  • Do you have other solution. Because, if I convert to gf(2), it takes very long time. So, I want to pefrom by mod operation. And I am using double type. How to use in int64 . i try it but have error Error using ^ MPOWER is not fully supported for integer classes. Both inputs must be scalar. – John Jan 12 '15 at 07:24
  • 2
    @Oliver Charlesworth Didierc's remark is reasonable, as only in the second approach the matrix is actually converted to GF(2). Still, this is not the solution as 'mod' and 'power' do commute - at least if you 'mod' with a prime number. – jolo Jan 12 '15 at 08:06
  • @jolo: Two ways just check the peform of matrix power in GF(2). Note that, A is double matrix, hence, A^30 will have the value from to 1..2^64-1. And mod operation to convert that result to 1 or 0 (GF(2)). This is solution 1. And for solution 2, I convert directly A matrix to gf2 and Power of matrix is performed in GF(2). However, the result of two ways are not similar. I think the problem is overflow problem – John Jan 12 '15 at 08:11
  • @user8264 Thanks. That's also how I understood your question. I just wanted to make clear that *in theory* the results should be equal. Thus I agree with you that it probably is a numeric problem. – jolo Jan 12 '15 at 09:41
  • 3
    @user8264 You might try to estimate when the overflow occurs and 'mod' before, e.g. use `mod(mod(A^10,2)*mod(A^10,2)*mod(A^10,2),2)`. You should check whether the exponent of 10 is already too big or not. – jolo Jan 12 '15 at 09:44
  • @jolo: My problem is found in this topic http://stackoverflow.com/questions/11623827/fast-exponentiation-for-galois-fields and I think the author has same problem with me. Your way is one options but it is inconvenience because we must check it is overflow or not. – John Jan 12 '15 at 09:57
  • OK,thank you guys now I understand. So, why don't you simply keep the second solution since it works ? – didierc Jan 12 '15 at 10:57
  • @didierc; Second solution takes long time to compute and convert to GF(2) (about 1 minute for my matrix) however the first way only takes 5 seconds. Hence, I am looking for a simple method or fast way to compute my matrix that achieves similar the second way – John Jan 12 '15 at 11:03
  • Maybe the first one is fast because it's wrong? – didierc Jan 12 '15 at 11:53
  • no, it just is overflow of number. let check my solution below that solves overflow of number but it still is slow – John Jan 12 '15 at 11:56
  • 1
    @jolo: mod and power don't commute: `(5 ^ 3) % 4` is not the same as `(5 % 4) ^ 3`. – Oliver Charlesworth Jan 13 '15 at 08:44
  • @OliverCharlesworth As I wrote at the end of my comment, they only commute if you `mod` with a prime number (this yields a field). – jolo Jan 13 '15 at 10:02
  • 1
    @OliverCharlesworth: I don't think I got your point, as `(5 ^ 3) % 4` and `(5 % 4) ^ 3` both equal `1`. Maybe using `6,3,4`. Also: If you take the same `mod 4` of the second equation again, they should be equal. – knedlsepp Jan 13 '15 at 15:19
  • @knedlsepp: Hmm, yes, bad example! – Oliver Charlesworth Jan 13 '15 at 17:29
  • @jolo: Sure, switching to a finite-field and computing powers commute. But computing mod isn't the same as switching to a finite field... – Oliver Charlesworth Jan 13 '15 at 17:33
  • @OliverCharlesworth It is. What's the difference in your opinion? – jolo Jan 13 '15 at 19:49
  • @jolo: Crudely speaking, working in a finite field is where the result of *every* operation is automatically computed with modulo arithmetic. "mod" is a one-time thing. – Oliver Charlesworth Jan 13 '15 at 21:09
  • @OliverCharlesworth That was too crude for me. The quotient ring `\mathbb{Z}/n\mathbb{Z}` certainly is a field for `n` prime. This is the set of equivalence classes. In particular, no calculation depends on which representative of each equivalence class I calculate with. In other words - it doesn't matter when I `mod`. And - if that doesn't convince you - I'd be willing to bet as many beers as you like that you can't come up with an example where `mod by a prime number` and `power` don't commute ;=) – jolo Jan 13 '15 at 21:16
  • @jolo: Interesting. That sounds like the kind of result I *probably* learnt many moons ago, and then fell out of my memory ;) – Oliver Charlesworth Jan 13 '15 at 21:22

0 Answers0