前言

在实战之前我真的没想到这会耗费我将近两个下午的时间，并且现在看来，很多不必要的错误的产生都是因为我的轻敌。正所谓谏以往以知来者，所以我想在进入正题之前先总结我的错误，也为后来人做个提醒。

1 对数学概念理解不清

作为一道算法实现题，对算法的理解是解决问题的关键，而算法中使用的数学概念“矩阵”则是理解算法本身的关键。我错误的将对三阶矩阵的行列式求和方法代入到其余矩阵上（也就是所谓的“想当然”），导致代码本身即使没有错误也不能输出正确的答案。

2 求快

因为使用了矩阵，再加上一开始我对算法扩展性的要求导致代码本身十分冗长。但我明知问题不能一时解决也要快速求解，导致很多函数出现了运算步骤上的错误。并且，由于一开始的方阵大小是不定的，所以我采用二阶指针加上动态内存申请，以至于数组越界编译器也没有报错，最后大大增加了debug的时间。

3 对VS不够熟悉

这个问题无解，我也不想用vs。

4 英文命名

某门课程的老师曾跟我们半开玩笑地抱怨过：“你们有些人写函数还用拼音，丢不丢人”。但在一些情况下，专业的英语名词复杂难记，而作者本身（我）英语水平也不够高，故而并没有追求全英文命名的必要性。即使一定要使用英文命名，如果一时半会记不住单词就该仔细备注，不能到最后代码写到一半都不知道自己正在编写的函数是要做什么。

多表代换1 加密过程

由于我没找到与此相关的较为详细的定义，这里我用自己的话简单概括。

我们给定一个n阶方阵A，并给出一段长度为n*m的明文和一个常数字母C，对于每组明文：

将每个明文字母按照a0-z25的顺序转换成数字，然后与矩阵进行运算，得到的数字加上C模26然后转换回字母，就是加密后的字母

2 解密过程

其实就是加密的逆运算。根据矩阵的性质，我们以加密方阵A的逆矩阵B对密文组进行运算，然后减去C模26即可。

#3 从矩阵到逆矩阵

我们有如下公式：

其中，矩阵的伴随矩阵为其每个元素a(x,y)的代数余子式*(-1)^(x+y)构成的矩阵的转置矩阵。

三阶矩阵的行列式求法为其循环中每个[左上-右下]元素的积之和减去[右上-左下]元素的积之和。

由于最后的结果要取模，而行列式的倒数与伴随矩阵的运算结果相当大的概率会出现很多分数。出于计算精度的考量，我们要对行列式的倒数先进行取模运算，然后再合并取模，最后的步骤如下图：

加密算法的C++实现

这个算法还有待改进的空间，因为我没有处理输入的明文不构成n的整数倍的情况。如果读者想要再行改进，可以考虑在encode/decode的加解密第一层循环里加上“如果下一个索引超出长度就跳出”的判断。

1 算法文件构成

-Substitution.h：功能函数的头文件。

-Substitution.cpp：功能函数的实现文件。

-main.cpp：主函数的文件。

2 Substitution.h

#pragma oncestatic int a[3][3]; //指向密钥矩阵的指针static int b[3][3]; //指向解密（伴随）矩阵的指针static int c; //常数系数static int z;//mod(1/|A|)int mode(int x); //循环运算int getcode(char a); //char转int（ascii）char recode(int a); //int转charint** mall2(int count); //给指针申请内存空间int* getint(char* str); //输入字符串转数字 //托iostream的福不需要输入数字转字符串void inputCipher();//输入密钥矩阵int getA(int x, int y); //获取3阶矩阵元素的代数余子式void getAdjugate(); //获取密钥矩阵的伴随矩阵int get3Algebra(); //三阶矩阵的行列式的值int get2Algebra(int s[2][2]); //二阶矩阵的行列式的值int mod(int a); //模运算int modDivi(int a); //分数的模运算（1/|A|）void encode(char *x); //加密void decode(char *x); //解密void ui(); //界面void _test(int ** s);

#include"Substitution.h"#include<stdlib.h>#include<iostream>#include<string.h>#include<math.h>using namespace std;int mode(int x) {    if (x >= 3) {        return x - 3;    }    else if (x < 0) {        return x + 3;    }    return x;}int getcode(char x) {    return int(x) - 97;}char recode(int a) {    return char(a + 97);}int* getint(char* str) {    int len = int(strlen(str));    int* re = (int*)malloc(sizeof(int)*(len));    for (int i = 0; i < len; i++) {        re[i] = getcode(str[i]);    }    return re;}void inputCipher() {    for (int x = 0; x < 3; x++) {        for (int y = 0; y < 3; y++) {            cout << "请输入第" << x << "," << y << ":";            cin >> a[x][y];        }    }    cout << "请输入常数系数：";    cin >> c;}int getA(int x, int y) { //去掉输入的行和列，将三阶矩阵变成二阶矩阵输出    int re[2][2];     for (int i = 0; i < 3 ; i++) {        for (int m = 0; m < 3; m++) {             if (i == x || m == y) {                continue;            }            else if (i > x && m > y) {                re[i - 1][ m - 1] = a[i] [m];            }            else if (i > x) {                re[i - 1][m] = a[i][m];            }            else if (m > y) {                re[i][m - 1] = a[i][m];            }            else if(m < y&&i < x) {                re[i][m] = a[i][m];            }        }    }    return get2Algebra(re);}void getAdjugate() {    for (int i = 0; i < 3; i++) {        for (int m = 0; m < 3; m++) { //遍历每个矩阵元素，求出其对应的伴随矩阵元素值            b[i][m] = getA(m, i)*pow(-1,i+m);        }    }}int get3Algebra() { //算出三阶矩阵的行列式的值    int sum = 0;    int plus = 1;    for (int i = 0; i < 3; i++) {        for (int m = 0; m < 3; m++) {            plus *= a[mode(m + i)][ m]; //循环求积，我真的觉得循环是个好概念，玩过贪吃蛇的都知道        }        sum += plus;        plus = 1; //复位plus    } //这是第一部分（+）的计算    for (int i = 0; i < 3; i++) {        for (int m = 0; m < 3; m++) {            plus *= a[mode(m + i)][mode(3 - m)];        }        sum -= plus;        plus = 1;    }    return sum;}int get2Algebra(int s[2][2]) {    return s[0][0] * s[1][1] - s[0][1] * s[1][0]; //二阶行列式公式}int mod(int a) { //整数的模    while (a < 0 || a >= 26) {        if (a < 0) {            a += 26;        }        else if (a >= 26) {            a -= 26;        }    }    return a;}int modDivi(int a) { //分数的模是找到一个x使得（a*x）%26=1    if (a == 0) {        return 0;    }    else{        for (int i = 0; i<256; i++) { //可以把i<256改成1之类的，反正是无所谓的            if ((a*i) % 26 == 1) {                return i;            }        }    }}void encode(char*x) {    cout << "密文为：";    int index = 0;    int* cipher = getint(x);    int length = _msize(cipher)/sizeof(cipher[0]);//明文的长度    int* re = (int*)malloc(sizeof(int)*length);    while(index < length){        for (int i = 0; i < 3; i++) {            re[index + i] = 0;            for (int m = 0; m < 3; m++) {                re[index + i] += a[i][m] * cipher[index + m];            }            re[index + i] = mod(re[index + i] + c);            cout << recode(re[index + i]);        }        index += 3;    }    cout << endl;}void decode(char* x) {    cout << "明文为：";    int index = 0;    int* cipher = getint(x);    int length = _msize(cipher) / sizeof(cipher[0]); //明文的长度    int* re = (int*)malloc(sizeof(int)*length);    for (int i = 0; i < length; i++) {        cipher[i] -= c; //减去常量    }    while (index < length) {        for (int i = 0; i < 3; i++) {            re[index + i] = 0;            for (int m = 0; m < 3; m++) {                re[index + i] += b[i][m] * cipher[index + m];            }            re[index + i] = mod(z*re[index + i] );            cout << recode(re[index + i]);        }        index += 3;    }    cout << endl;}void ui() {    int swi;    inputCipher();    cout << "生成解密矩阵中。。。" << endl;    getAdjugate(); //获取伴随矩阵    z = modDivi(abs(get3Algebra()));    char m[2566];    while (1) {        cout << "请输入你需要的操作：" << endl << "1.加密" << endl << "2.解密" << endl << "3.退出" << endl;        cin >> swi;        switch (swi) {        case 1:            cout << "请输入：";            cin >> m;            encode(m);            break;        case 2:            cout << "请输入：";            cin >> m;            decode(m);            break;        case 3:            return;        }    }}

#include"Substitution.h"int main() {    ui();    return 0;}