Быстрое матричное возведение в степень в поле Галуа

Я ищу быстрый способ вычисления степени матрицы A в поле Галуа 2 (GF(2) ). A — двойная матрица, и ее возведение в степень x обозначается

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

Простой способ заключается в том, что преобразует A в GF (2) (поскольку данная матрица A является двойной матрицей), а затем выполняет операцию возведения в степень. Код Matlab

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

Однако этот способ занимает много времени, чтобы преобразовать матрицу A в GF (2). Я ищу быстрый способ без преобразования GF (2). То есть я использую операцию мода

A_pow_x_second = mod(A^x, 2)

Однако проблема в том, что результат первого и второго способа не похож. Проблема в том, что переполнение числа. Один член предложил мне преобразовать матрицу A в int64. Тем не менее, я думаю, что это не лучший способ справиться с моей проблемой. Не могли бы вы предложить мне быстрый способ сделать это в Matlab? заранее спасибо

Это простой пример

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

Первый способ,

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

Результат:

 0           1           0
 1           0           0
 0           0           1

Второй способ

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

A_pow_x_second =

     0     0     0
     0     0     0
     0     0     0

Как быстро вычислить A^x без преобразования в GF(2), который имеет аналогичный результат в первом случае?


matlab algorithm matrix galois-field
person John    schedule 12.01.2015    source источник
comment
возможный дубликат Матричное возведение в степень в поле Галуа 2   -  person knedlsepp    schedule 12.01.2015
comment
Также: Поскольку вы продолжаете спрашивать об этой статье: вместо вычисления (A^i)*b вы должны вместо этого вычислить A*(A*(..*(A*b))) [mod 2] с помощью цикла for! И, конечно же, для вычисления (A^(i+1))*b) вы должны повторно использовать результат предыдущего вычисления A*(A^i)*b.   -  person knedlsepp    schedule 12.01.2015
comment
Проблема, с которой вы столкнулись, заключается не в переполнении, а в ограниченной точности типа данных double. MATLAB (и IEEE 754) используют 52 бита для дроби и 11 бит для экспоненты. С 52 битами для дроби вы получите точность около 16 цифр в десятичной системе. Этого никогда не бывает достаточно для тех ценностей, которые у вас есть.   -  person hbaderts    schedule 12.01.2015
comment
@knedlsepp: да, в этой теме я просто нахожу проблему, и я обнаружил, что эта проблема связана с переполнением. И я создаю новую тему сейчас, чтобы решить эту проблему. В теме я также нахожу быстрый способ вычислить мощность матрицы, чтобы избежать переполнения числа.   -  person John    schedule 12.01.2015
comment
@knedlsepp: В каком предложении говорится о моей проблеме в этой статье. Это действительно проблема, которую я решаю для этой статьи. Заранее спасибо.   -  person John    schedule 12.01.2015
comment
@hbaderts: Хороший вопрос. Вы предлагаете мне какой-то быстрый способ решить мою проблему. Чтобы получить более подробную информацию, обратитесь к теме поле 2"> stackoverflow.com/questions/27896346/   -  person John    schedule 12.01.2015
comment
@ user8264: Не могли бы вы присоединиться ко мне в чате?   -  person knedlsepp    schedule 12.01.2015