• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>SIAM Journal on Discrete Mathematics >DECIDING ORTHOGONALITY IN CONSTRUCTION-A LATTICES
【24h】

DECIDING ORTHOGONALITY IN CONSTRUCTION-A LATTICES

机译：决定构造中的正交性

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Lattices are discrete mathematical objects with widespread applications to integer programs as well as modern cryptography. An important class of lattices are those that possess an orthogonal basis, since if such an orthogonal basis is known, then many other fundamental problems on lattices can be solved easily (e.g., the Closest Vector Problem). However, intriguingly, deciding whether a lattice has an orthogonal basis is not known to be either NP-complete or in P. In this paper, we focus on the orthogonality decision problem for a well-known family of lattices, namely Construction-A lattices. These are lattices of the form C+qZ', where C is an error-correcting q-ary code, and are studied in communication settings. We provide a complete characterization of lattices obtained from binary and ternary codes using Construction-A that have an orthogonal basis. We use this characterization to give an efficient algorithm to solve the orthogonality decision problem. Our algorithm also finds an orthogonal basis if one exists for this family of lattices.
机译：格是离散的数学对象，在整数程序以及现代密码学中都有广泛的应用。一类重要的格子是具有正交基的格子，因为如果知道这样的正交基，则可以容易地解决格子上的许多其他基本问题（例如，最近向量问题）。然而，有趣的是，确定一个晶格是否具有正交基础不知道是NP完备的还是P中的。在本文中，我们关注于一个著名的晶格族（即A型晶格）的正交性决策问题。 。这些是C + qZ'形式的晶格，其中C是纠错q码，并在通讯设置中进行研究。我们提供了使用具有正交基础的Construction-A从二进制和三进制代码获得的晶格的完整表征。我们使用该特征来给出解决正交性决策问题的有效算法。我们的算法还找到正交基（如果存在这一族的晶格）。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号