摘要：在信息论和密码学中,线性码有各种不同的应用.其中随机线随性码有很多困难问题,如伴随式译码问题是已知的NP-hard问题.随机线性码的译码问题是基于纠错码的密码方案所依赖的计算困难问题.它是抵抗量子计算机攻击的候选方案之一.关于这一问题的求解方法目前仍然是指数时间的,但最优译码算法的运行时间也在不断改善,其中信息集译码的Stern算法^([4]),其运行时间复杂度为■(2^(0.05563n)).最近,May等人设计了MMT算法^([6]),使得运行时间复杂度降为■(2^(0.05363n)),空间复杂度降为■(2^(0.021n)).May等人提出伴随式译码的子问题,即子矩阵匹配问题,这使得我们可以寻找更加有效的方法来解决进而解决伴随式译码问题.针对May提出的MMT算法及其优化的参数,我们提出一种改进MMT算法,主要的改进有两方面,首先,分解索引的枚举范围,然后是索引集合的大小;主要的思路依然是集中在列表的生成方式上,得到的时间复杂度为■(2^(0.05310n)),空间复杂度为■(2^(0.0144n)).改进后的MMT算法不但在时间上有所提高,而且在空间上占有一定的优势.近期May等提出了Nearest Neighbor算法,它的在时间复杂度上占有绝对的优势,以后的工作可以分析Nearest Neighbor算法,对MMT算法进一步提高.