1

Надо реализовать шифр Хилла с матрицей 3х3.
Проблема:
Неправильно считается обратная матрица(
Из этого примера wiki матрица у меня получается такая (и вручную и программно):
8 5 21
21 8 14
10 5 8
Как они ее там получили? Я считаю: (1/det)*A[3][3], где det - детерминант, A[3][3] - матрица дополнений. Если элемент отрицательный прибавляю 26 пока он не станет положительным, а затем остальные элементы по модулю 26. Детерминант сходится (det=441), решение сравнения сходится (x=25), а вот матрица в итоге нет.

Если надо - выложу код. Но дело не в нем, а непонимании подсчета обратной матрицы.

2 ответа 2

5

Вы, видимо, не так берете обратный детерминант.

Предполагаю, что вы правильно вычислили матрицу обратных дополнений. Первая строка в ней

70 5 -99.

После приведения по модулю 26 получаем

18 5 5.

Умножаем на 1/det(A). Обратите внимание, что тут не просто деление, а мультиплкативная инверсия, поэтому они там в примере для нее и получили 25. Считать можно через расширенный алгоритм Евклида. Поищите "multiplicative inverse {your language}", наверняка что-то найдете (в Java можно воспользоваться встроенным BigInteger.modInverse). Так вот, умножаем на 25:

450 125 125.

Сравниваем по модулю с 26:

8 21 21.

После транспонирования это будет первый столбец.

1
  • Это уже больше похоже на правду...
    – Ray
    18 окт 2011 в 21:21
1

Есть под рукой код метода Гаусса с приписыванием единичной матрицы. В результате работы в массиве E получается обратная матрица.

int N;
int i, j, k;

ifstream infile("matrix.txt");
infile >> N;

double *A = new double[N*N];

for ( i = 0; i < N; i++ )
    for ( j = 0; j < N; j++ )
        infile >> A[i*N+j];

double *E = new double[N*N];
for ( i = 0; i < N; i++ ) {
    for ( j = 0; j < N; j++ ) 
        E[i*N+j] = 0;
    E[i*N+i] = 1;
}

double pivot;
for ( i = 0; i < N; i++ ) {
    pivot = A[i*N+i];
    for( j = 0; j < N; j++ ) {
        A[i*N+j] /= pivot;
        E[i*N+j] /= pivot;
    }

    for( j = 0; j < N; j++ ) {
        if ( i == j ) continue;

        pivot = A[j*N+i];
        for( k = 0; k < N; k++ ) {
            A[j*N+k] -= (A[i*N+k]*pivot);
            E[j*N+k] -= (E[i*N+k]*pivot);
        }
    }
}
2
  • Там вся арифметика ведется по модулю 26.
    – Ray
    18 окт 2011 в 8:25
  • Будет время - сделаю вариант с модульной арифметикой.
    – renegator
    18 окт 2011 в 9:44

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.