关于一类代数图及其在纠错编码和密码学中的应用的研究

本项目主要研究Lazebnik等人提出的代数二部图D(k,q)及其推广图的各种代数性质，并以此基础探讨这些图在纠错编码与密码学中的应用，属于信息科学与数学的交叉研究。主要研究内容和研究目标包括：1）通过发展一些新的组合方法，对D(k,q)的一些特殊路径进行深入研究，证明关于D(k,q)的围长的猜想在一些新情形下的正确性；2）全面研究D(k,q)的一类推广图的对称性、连通性和围长等代数性质，给出可逼近极图理论中一些经典的上下界的新图族；3）系统研究D(k,q)及其推广图在构造LDPC码方面的应用，利用其多重提升的具体代数结构分析码率、最小汉明距离、停止集、陷落集和吸收集等与纠错性能密切相关的几类重要因素，得到具有良好纠错性能的LDPC码的新的代数构造方法。探索研究D(k,q)及其推广图与一些经典的密码算法的结合，设计一些安全性高的对称或公钥密码体制。

The main subjects investigated in this project are the algebraic bipartite graph D(k,q), proposed by Lazebnik et.al, and its gerneralizations. We will investigate the algebraic properties of these graphs and their applications in error-correcting and cryptology. The main research contents of this project include: 1) Study in depth some special paths in D(k,q) by developing some new combinatorial methods, and then prove the correctness of the conjecture on the girth of D(k,q) under a few new conditions; 2) Study a class of generalized graphs of D(k,q) in its entirety about the symmetry, connectivity and girth, and then find some new families of finite graphs which can approach some classical bounds in extremal graph theory; 3) Study systematically the applications of D(k,q) and its generalizations for the construction of LDPC codes, by utilizing the algebraic constructures of the graphs to analysis the important factors of the decoding of the codes, such as their code rates, minimal Hamming distances, stopping sets, trapping sets and absorbing sets, and then propose some new algebraic constructions for LDPC codes with good error performance. Explore the combination of D(k,q) and its generalizations with some classical cryptographic algorithms so as to design some new symmetrical cryptosystems or public-key cryptosystems with high security.