Algorithmic Problems in Number Theory

研究人员发现，对于非常大的输入， 大小，现代因式分解算法，如数域筛选 可以在每个处理器的内存比以前少得多的情况下执行 以前相信。因此，对于非常大的d值， 数字域筛选器可以以相同的成本分解3D数字 以前认为这是d位数所需的。的 调查人员正在研究这一做法的实际效果。 对于小的输入大小，例如1024位和1536位，可以使用发现。的 研究人员也在继续研究 Krull维数为1的交换环中的计算工具。 数域筛子是对许多公钥密码体制最著名的攻击 密码系统用来保护的秘密和真实性 互联网通信。理解这个算法的力量是 在为密码系统选择安全的密钥大小时至关重要。如果由于 例如，犯罪分子可以分解高达1024位的整数， 用户必须选择大于1024位的密钥大小。 该奖项由代数，数论和 组合数学程序与数字、符号和几何 计算程序。

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.