Algorithmic Problems in Number Theory

数论中的算法问题

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

The number field sieve is the latest algorithm for factoring integers into primes. The investigator will continue his research into the speed of the number field sieve. The plan is first, to study the precise distribution of certain vectors constructed in the number field sieve; second, to develop tools to analyze the probability that vectors chosen from a non-uniform distributimn will be independent; third, combine these results to sharpen the known heuristics for the time taken by the number field sieve. The investigator will also consider various problems in multiprecision arithmetic from a geometric viewpoint. This research falls into the general mathematical field of Number Theory. Number theory has its historical roots in the study of the whole numbers, addressing such questions as those dealing with the divisibility of one whole number by another. It is among the oldest branches of mathematics and was pursued for many centuries for purely aesthetic reasons. However, within the last half century it has become an indispensable tool in diverse applications in areas such as data transmission and processing, and communication systems.

数域筛法是将整数分解成素数的最新算法。调查员将继续他对数字域筛子速度的研究。我们的计划是，第一，研究在数字域筛子中构造的某些向量的精确分布；第二，开发工具来分析从非均匀分布中选择的向量将独立的概率；第三，结合这些结果来改进数字域筛子所花费的时间的已知启发式。研究人员还将从几何角度考虑多精度运算中的各种问题。这项研究属于数论的一般数学领域。数论的历史根源在于对整数的研究，它解决了一些问题，比如一个整数被另一个整数整除的问题。它是数学中最古老的分支之一，出于纯粹的美学原因，人们追寻了许多个世纪。然而，在过去的半个世纪里，它已经成为数据传输和处理以及通信系统等领域的各种应用中不可或缺的工具。