Добрый день! Подскажите, пожалуйста чайнику, как производится вычитание, умножение, деление по модулю 2. Очень нужно найти определитель и обратную матрицу к двоичной. Заранее большое спасибо!
Ну слушай Дашша! Сложение и вычитание - XOR умножение и деление - AND что такое эти XOR и AND - предлагаю разобраться самостоятельно. Обращение матрицы ничем не отличается от гаусса или жордана для обычных чисел. Ясен глаз, нужна перестановка строк чтобы не делить на ноль. А перестановка столбцов не нужна, тк ошибок округления нет. Детерменант - это просто 0 или 1 в зависимости от того вырождена матрица или нет. Находится приведением матрицы к треугольному виду.
Вот еще, вероятность того что случайная двоичная матрица невырождена довольна высока и равна 28%. Стало быть с третьего раза получится =)))
Добрый день! Пожалуйста, помогите еще раз! Не могу найти ошибку в коде. Нужно найти обратную матрицу с помощью верхнетреугольной (системой линейных уравнений). for i:=n-1 downto 0 do begin j:=i+1; while (j<n) do begin o[i,k]:=o[i,k]-(z[i,j]*x[j,k]); j:=j+1 end; x[i,k]:=o[i,k]/z[i,i] end o - единичная матрица, z - исходная матрица, преобразованная к верхнетреугольному виду, x - искомая матрица.
Дашш... А ты эта... мальчонка или девчонка? Получай курсовую работу целиком! Надеюсь, разберешься что к чему... Код (Text): {$APPTYPE CONSOLE} const N=10; type Field=byte; type matrix=array of array of Field; var U,A,B,At:Matrix; procedure GetMemory(var a:Matrix); var i:Cardinal; begin SetLength(a,N); i:=0; while i<N do begin SetLength(a[i],N); inc(i); end; end; procedure FreeMemory(var a:Matrix); var i:Cardinal; begin i:=0; while i<N do begin SetLength(a[i],0); inc(i); end; SetLength(a,0); end; procedure PrintMatrix(var a:Matrix); var i,j:Cardinal; begin i:=0; while i<N do begin j:=0; while j<N do begin write(a[i,j]:2); inc(j); end; writeln; inc(i); end; end; procedure MultMatrix(var c,a,b:Matrix); var i,j,k:Cardinal; begin i:=0; while i<N do begin j:=0; while j<N do begin c[i,j]:=0; k:=0; while k<N do begin c[i,j]:=c[i,j] xor (a[i,k] and b[k,j]); inc(k); end; inc(j); end; inc(i); end; end; procedure CopyMatrix(var a,b:Matrix); var i,j:Cardinal; begin i:=0; while i<N do begin j:=0; while j<N do begin a[i,j]:=b[i,j]; inc(j); end; inc(i); end; end; procedure GetRandomMatrix(var a:Matrix); var i,j:cardinal; begin i:=0; while i<N do begin j:=0; while j<N do begin a[i,j]:=Random(2); inc(j); end; writeln; inc(i); end; end; procedure GetUnityMatrix(var a:Matrix); var i,j:cardinal; begin i:=0; while i<N do begin j:=0; while j<N do begin if i=j then a[i,j]:=1 else a[i,j]:=0; inc(j); end; inc(i); end; end; function InvMatrix(var a,b:Matrix):boolean; var i,j,k:Cardinal; tmp:Field; begin i:=0; while i<N do begin j:=i; while (j<N) and (a[j,i]=0) do inc(j); if j=N then begin Result:=false; Exit; end; if i<>j then begin k:=0; while k<N do begin tmp:=a[i,k]; a[i,k]:=a[j,k]; a[j,k]:=tmp; tmp:=b[i,k]; b[i,k]:=b[j,k]; b[j,k]:=tmp; inc(k); end; end; j:=i+1; while j<N do begin if a[j,i]<>0 then begin k:=0; while k<N do begin a[j,k]:=a[j,k] xor a[i,k]; b[j,k]:=b[j,k] xor b[i,k]; inc(k); end; end; inc(j); end; inc(i); end; i:=0; while i<N do begin j:=i+1; while j<N do begin if a[N-1-j,N-1-i]<>0 then begin k:=0; while k<N do begin a[N-1-j,N-1-k]:=a[N-1-j,N-1-k] xor a[N-1-i,N-1-k]; b[N-1-j,N-1-k]:=b[N-1-j,N-1-k] xor b[N-1-i,N-1-k]; inc(k); end; end; inc(j); end; inc(i); end; Result:=true; end; BEGIN GetMemory(A); GetMemory(B); GetMemory(At); GetMemory(U); Randomize; //RandSeed:=11; GetRandomMatrix(A); GetUnityMatrix(U); CopyMatrix(B,A); if not InvMatrix(B,U) then begin writeln('Matrix is singular'); Exit; end; CopyMatrix(At,U); MultMatrix(U,A,At); PrintMatrix(U); MultMatrix(U,At,A); PrintMatrix(U); FreeMemory(A); FreeMemory(B); FreeMemory(At); FreeMemory(U); end.
Добрый день! Хотел узнать Ваше мнение. Можно ли рассматривать операцию сложение по модулю два для пары слов (Pn....P2P1P0 XOR Kn.....K2K1K0) или по простому (P XOR K), где Pn n-разрядное слово открытого текста, а Kn- n-разрядный ключ, как управляемый ключем S-блок подстановки? Если нет, то интересно как тогда выглядит S-box, управляемый ключем, а не с жёсткой логикой.
Nafanya, S-подстановка (мы говорим о DES-подобных шифрах, да?) обычно фиксирована, хотя ничто не мешает генерировать её матрицу на основе ключа. Единственное «но» — криптостойкость полученного алгоритма. S-boxes товарищи специально рисовали руками для обеспечения эвеланш-эффекта. Будет ли сгенерёная обеспечивать — вопрос.
Да..., у DES лавинный эффект просто грандиозный! Изменение 1 бита открытого текста влияет на 29 бит шифротекста! Изменение приблизительно в 1,5 процентах исходного текста создают изменение приблизительно 45 процентов зашифрованного текста. Круто конечно. baldr А вы встречали s-блок, управляемый ключем? В DES'е такого нет, там ключ раунда вводит отбеливатель после p-блока расширения 32-48 бит.
Nafanya, Как работает DES — я в курсе, спасибо. Основной вклад в лавинное накопление отличий там вносит всё-таки метод Фейстеля (многие называют это сетью, а я против: не всякий орграф — полноценная сеть . Тут как с LCG/CRC: только тщательно подобранные константы дают желаемый результат (ну или нечто приближённое).
