关于一道编程题的思考

编程

一道普通的编程题

以下这道编程题连续三年出现在本科《计算机安全学》的实践作业当中，每年大概会有100名左右的学生被要求用C或者Python实现相关功能。

给定以下8*8的0/1比特矩阵M，

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

请编程实现M*x（矩阵乘向量），x是8比特的0/1向量。即，输入x，输出M*x的值。其中所有乘法、加法都是mod 2的乘法、加法。编程语言请使用C或者Python。

今天拿出来讨论主要不是因为这道题的结题思路有什么难或多有价值，也没有什么特殊的技巧需要总结，而是因为，大部分同学的程序没有能够体现出程序员应有的基本素养。他们的想法大多与我不同。

题解

题目描述的是一种普通的矩阵运算。这个矩阵出现在著名的分组加密算法AES的设计当中，用于生成AES算法中使用的S-box（一般读者并不需要理解什么是S-box）。为方便论述，本文简化了其中关于GF(2^8)的描述，也砍掉了一个xor某常数的过程。不过，过程大致类似。

大部分同学的做法是这样的：

//AES给出的常数矩阵
const bool N[8][8] = {1, 0, 0, 0, 1, 1, 1, 1, 
                      1, 1, 0, 0, 0, 1, 1, 1, 
                      1, 1, 1, 0, 0, 0, 1, 1, 
                      1, 1, 1, 1, 0, 0, 0, 1, 
                      1, 1, 1, 1, 1, 0, 0, 0, 
                      0, 1, 1, 1, 1, 1, 0, 0,
                      0, 0, 1, 1, 1, 1, 1, 0,
                      0, 0, 0, 1, 1, 1, 1, 1}; 
//将输入x转化为数组用作矩阵运算 
for(int i = 0; i < 8; i ++)
  { xb[i] = (x&1); x >>= 1; } 
//矩阵乘法 
bool tmp[8]; 
for(int i = 0; i < 8; i ++)
  tmp[i] = 0; 
for(int i = 0; i < 8; i ++)
      for(int j = 0; j < 8; j ++)
          tmp[i] ^= (N[i][j] & xb[j]); 
//输出结果
.......

程序员把功能实现出来不就好了吗？你告诉我需要一个矩阵乘法，我做出来了有什么不对？没有不对，这个功能是对的。但是，当我们用一种数学的语言去描述功能的时候，我们只是描述，“翻译”成应用的时候需要另一种“语言”。听上去有点玄，其实这才是程序员应有的素养。以下还是回到题目来解释。

矩阵

题目给出的是一个矩阵，每个元素都是0/1比特，8行8列。难道8比特没让程序员们有什么想法？为什么存储8比特的应该是数组而不是一个unsigned char？比如，这个矩阵难道不应该是：

unsigned char M[] = {0x1F, 0x3E, 0x7C, 0xF8, 0xF1, 0xE3, 0xC7, 0x8F};

矩阵乘向量

矩阵乘向量，无非是矩阵列向量的组合。模2加法在这里只是比特按位异或（xor）。大致应该是以下这样一种运算(注意以下代码不是完全正确的C语言程序)：

res = 0x00;
for(int i = 0; i < 8; i ++)
    res = res ^ (M[i] * xb[i])

向量x是不是应该转换为是一个数组xb？答案否定！我们可以通过位移操作得到相应的比特。并且还必须注意一点，当x中的比特为0，那么对应的列就没必要参与操作了。所以，

res = 0x00;
i = 0;
//矩阵列组合，直到x小于0
while(x > 0)
{
    if(x % 2 == 1) //取最低位比特，并且忽略比特0的加法
        res ^= M[i] ;
    i++; //为什么不在上面的i上进行++ ?
    x /= 2; //可用比特移位操作。但是你认为这样除效率会比移位要差吗？
}

延伸思考

单纯从题目本身看，并不很重要，重要的是要思考。

“会”不等同“素养”

归纳一下我想强调的所谓程序员的素养：
- 熟悉数字的十六进制表达；
- 熟悉变量的比特运算；
- 熟悉矩阵的列组合；
- xor与模2运算的关系；
- 知道变量最低比特位如何取；
- 知道整除2就是变量右移一比特；

这些你单独拿出来考试，请问谁不会？都会！哪请问，为什么到了具体编程的时候大部分人不会？会不等同于素养！素养是什么？是对基础知识的融会贯通，是让专业知识溶入你的血液。

关于语言的应用

也许有人会问了，AES的设计者为什么需要这样的矩阵描述，而不是直接给出后面这种描述？你告诉我矩阵是这8个常量不就好了，为什么要我们去“猜”？

答案是，AES的设计者需要一种数学语言来描述这个过程。请注意，是一种需要。为什么？主要两个原因。首先，因为设计人员想展示这个矩阵具有可逆矩阵，可用于求逆S-Box的元素。如果我告诉你这几个常量，而不是展示一个矩阵，那么矩阵的熟悉就难以表达。而现在则简单，你只需要自己验证M矩阵行列式不为0即可。其次，设计者还想传递一个公开的想法，矩阵构造的规律性。大家可以自己验证矩阵每一行每一列之间的关系。

当这种语言描述的目的达到了，那么我们就需要另一种“语言”来执行相关操作，达到既定目标。其实，在实现中，这个矩阵M并不一定真正存在。给定输入b，输出b'满足以下关系定义，这估计才是设计者的真实想法：

我们可以使用什么样的比特操作来得到正确的答案呢？答案并不重要，也不是本文想论述的内容。大致如下，但不再分析：

//ROTL8是8比特变量的循环左移
xformed = x ^ ROTL8(x, 1) ^ ROTL8(x, 2) ^ ROTL8(x, 3) ^ ROTL8(x, 4)

啥？一条命令完成？？？看到这里，你们会不会觉得我是抛出一个假问题，然后给出了一个假答案？思考才是这个帖子的本意。

多说一句，至此故事并没有结束。AES的构造描述在很多年之后依然有新的研究进展。 文章“Essential Algebraic Structure Within the AES” （by Murphy and Robshaw）关注的不是实现，而是AES的构造与分析，详情不在本文展开，有兴趣可以参考这里。

总结

数学语言可以有助于我们清楚地表达许多思想，能充分理解数学语言应该是程序员的应有素养。程序设计语言是一种表达思想的工具，它不是单纯用于重述或重现现实的语言，它应该是对数学语言系统化的工具，很好地描述数学，又能体现系统属性，诸如高效性、兼容性等。

如果要简单地看待这篇文章，你只需要记住：编程并不是用程序语言依葫芦画瓢。SICP对此已经做了非常深入的探讨，建议大家阅读。