Algorithmic Problems in Number Theory

数论中的算法问题

• 批准号: 0140542
• 负责人: Daniel Bernstein
• 金额: --
• 依托单位: University of Illinois at Chicago
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-07-01 至 2007-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0140542&HistoricalAwards=false
• 关键词: Algorithmic; Problems; Number; Theory

The investigator has discovered that, for extremely large input sizes, modern factorization algorithms such as the number-field sieve can be carried out with far less memory per processor than was previously believed. Consequently, for extremely large values of d, the number-field sieve can factor 3d-digit numbers at the same cost that was previously believed to be required for d-digit numbers. The investigator is studying the practical effectiveness of this discovery for small input sizes, such as 1024 bits and 1536 bits. The investigator is also continuing his research into the fundamental computational tools in commutative rings of Krull dimension 1. The number-field sieve is the best known attack on many public-key cryptosystems used to protect the secrecy and authenticity of Internet communications. Understanding the power of this algorithm is essential in choosing safe key sizes for the cryptosystems. If, for example, criminals can factor integers as large as 1024 bits, then users must choose key sizes larger than 1024 bits. This award is being cofunded by the Algebra, Number Theory, and Combinatorics Program and the Numeric, Symbolic, and Geometric Computation Program.

研究人员发现，对于极大的输入大小，像数字域筛选这样的现代因式分解算法可以在每个处理器上使用比之前认为的要少得多的内存。因此，对于极大的d值，数字域筛选器可以对3D数字进行分解，其代价与以前认为的d数字所需的成本相同。研究人员正在研究这一发现对于小输入大小的实际效果，例如1024位和1536位。这位研究人员还在继续他对1维Krull交换环中基本计算工具的研究。数字域筛子是对许多用于保护互联网通信的保密性和真实性的公钥密码系统的最著名的攻击。了解该算法的强大功能对于为密码系统选择安全密钥大小至关重要。例如，如果犯罪分子可以将整数分解为1024位，那么用户必须选择大于1024位的密钥大小。该奖项由代数、数论和组合数学计划以及数值、符号和几何计算计划共同资助。