探索拓扑编码中的图格与传统格的联系  

Exploring Relationship Between Traditional Lattices and Graph Lattices of Topological Coding

作　　者：张明军 杨思华 姚兵 ZHANG Mingjun;YANG Sihua;YAO Bing(China Northwest Center of Financial Research,Lanzhou University of Finance and Economics,Lanzhou 730020,China;School of Information Engineering,Lanzhou University of Finance and Economics,Lanzhou 730020,China;Key Laboratory of E-Business Technology and Application of Gansu Province,Lanzhou 730020,China;College of Mathematics and Statistics,Northwest Normal University,Lanzhou 730070,China)

机构地区：[1]兰州财经大学中国西北金融研究中心,兰州730020 [2]兰州财经大学信息工程学院,兰州730020 [3]甘肃省电子商务技术与应用重点实验室,兰州730020 [4]西北师范大学数学与统计学院,兰州730070

出　　处：《计算机科学与探索》2021年第11期2171-2183,共13页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金(61363060,61662066);甘肃省技术创新引导计划:软科学专项(21CX1ZA285);兰州财经大学中国西北金融研究中心项目(JYYZ201905);兰州财经大学高等教育教学改革研究项目(LJZ202012)。

摘　　要：已知不存在解决某些格困难问题的多项式量子算法,无色图格和着色图格是受格理论启发而产生的多学科交叉的产物。拓扑编码中的一个无色图格或着色图格是建立在图的运算和一组顶点不交的连通图或连通着色图构成的图格基上。基于口令认证或数字文件加密,介绍数字串拓扑认证问题,用拓扑编码给出一种非对称加密系统。拓扑编码可以形成一个公钥对应多个私钥,多个公钥对应多个私钥的非对称加密系统;拓扑编码中的拓扑认证需要两个不同领域的数学知识,而且可以产生指数级别的算法。基于图的边连接运算、顶点重合运算等运算,研究了具有优美全着色的着色图格基存在性,建立了边连接图格和F-图格等无穷图格,并证明这些图格对优美全着色具有封闭性。定义了特殊着色图的拓扑向量,建立了图格与非负整数传统格之间的一个联系,为抗量子计算提供可行的技术;说明没有多项式算法解决数字串分解问题,又因为图同构问题是NP-困难,从而拓扑编码建立的图格具有抗超大计算机和量子计算机的计算功能。It is known that there are no polynomial quantum algorithms to solve some lattice difficult problems.Uncolored graphic lattice and colored graphic lattice are the products of multidisciplinary intersection inspired by lattice theory.A uncolored graphic lattice or a colored graphic lattice in topological coding is based on some graph operations and a set of disjoint connected graphs or disjoint connected colored graphs.Based on password authentication or digital file encryption,this paper introduces the number-based string topological authentication problem,and gives an asymmetric encryption system by topological coding.Topological coding can form an asymmetric encryption system with one public key corresponding to two or more private keys and,more public keys corresponding to more private keys.Topology authentication in topology coding requires two different fields of mathematical knowledge and can produce exponential level algorithm.Based on the edge-joining operation and vertex-coinciding operation of graphs,the existence of colored graphic lattice admitting graceful total colorings is shown,and graphic lattice and F-graphic lattice are established with infinite elements closed to graceful total coloring.Topological vectors for special coloring graphs are defined,and a connection between graphic lattice and non-negative integer traditional lattice is built up to provide a feasible technique for quantum resistance calculation,since there is no polynomial algorithm for solving number-based strings up to now.Because graph isomorphism problem is NP-hard,topological coding lattice has the function of resisting supercomputer and quantum computer.

关 键 词：格 图格 全着色 优美标号 拓扑编码 网络安全 

分 类 号：O157.5[理学—数学]