论文部分内容阅读
在信息论和密码学中,线性码有各种不同的应用.其中随机线随性码有很多困难问题,如伴随式译码问题是已知的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算法进一步提高.
In information theory and cryptography, there are a variety of different applications of linear codes, among which there are many difficult problems with random line random codes, such as the concurrency decoding problem is a known NP-hard problem.The decoding of random linear codes It is one of the candidate schemes to resist the attack of quantum computer, and the solving method of this problem is still exponential at the present time, but the running time of the optimal decoding algorithm is also (2) (0.05563n)). Recently, May et al. Designed the MMT algorithm ~ ([6]) to improve the performance of the Stern algorithm [4] (2 ~ (0.05363n)), the space complexity is reduced to (2 ~ (0.021n)). May et al. Proposed a sub-problem of subordinate decoding, namely the sub-matrix matching problem , Which allows us to find a more effective way to solve and then solve the concurrency decoding problem.For the proposed MMT algorithm and its optimization parameters, we propose an improved MMT algorithm, the main improvements in two ways, first of all, decomposition Index enumeration range, then the size of the index collection; The main idea is still The time complexity obtained is (2 ~ (0.05310n)) and the space complexity is (2 ~ (0.0144n)). The improved MMT algorithm not only improves in time , But also has certain advantages in space.May recently proposed the Nearest Neighbor algorithm, which has the absolute advantage in time complexity, and can analyze the Nearest Neighbor algorithm in the future and improve the MMT algorithm further.