Algorithms for Algebraic Number Theory

这个项目旨在开发新的算法，以帮助计算数论和其他计算数学、科学和工程领域的研究人员。自从多核台式计算机出现以来，就一直存在对能够利用计算技术的最新进步的算法的需求。许多当前的算法不能被分成多个部分并在单独的计算核心上运行。相反，这些算法需要完全重新设计。在计算数论中，这一点最为真实。然而，该数学领域中使用的许多基本技术与其他数学领域中使用的技术相似或相同。例如，用于乘以非常大的多项式的快速算法利用快速傅立叶变换，这是一种在信号处理、数学建模和许多其他领域中使用的技术。为了便于设计新的算法，选择了计算数论中的一些有趣的问题。第一种是计算被称为希尔伯特模形式的大型表格。这些数学函数应用于广为人知的费马最后定理的推广，并与椭圆曲线理论有联系，该理论在安德鲁·威尔著名的定理证明中使用。第二个问题是检验一个被称为Vandiver猜想的猜想。这一数字理论猜想被广泛认为是正确的，但启发式方法表明，我们还没有对其进行足够深入的检查，无法获得任何确定性。我们可以粗略地预测到目前为止我们应该找到多少反例，如果存在的话，而且很可能不到一例。我们也知道检查到什么程度才能给我们一个很好的机会找到反例，这也是该项目的目标之一。该项目的第三部分涉及数据传输的安全，例如通过互联网和大公司之间的传输。数据是安全的，并使用数学“密钥”进行传输。在RSA加密方法中，要解密这样的消息，只需将大数分解为素数。执行此操作的最佳技术是数字字段筛选器。我们的目标是利用多项式运算和筛选的新技术来改进数字域六。另一种可以从筛选的改进中受益的技术是索引演算，它被用来攻击一种称为椭圆曲线密码系统的密码系统。我们的目标也是将我们的知识应用到这个问题上，以确保我们在个人和财务数据安全受到的潜在攻击中保持领先地位。该项目的第四部分涉及提高基本“核心”算术计算的速度。许多研究人员和公司依赖于多项式算术和线性代数中的某些基本算法来完成他们的大部分计算工作。从飞机设计到计算机软件，一切都依赖于快速计算，归根结底就是这些基本算法。该项目首席研究员的最新进展对许多基本算法具有戏剧性的影响。加速这样的基本计算是这个项目的一个具体目标。最后一个项目与计算被称为组的数学对象的结构有关。粗略地说，群衡量的是物体的对称性，而计算它们的结构是许多数学的基础。要做的具体研究将利用筛分技术，如数域筛分，来改进目前计算数学群结构的算法。从理解宇宙的结构到安全传输数据的代码，一切都依赖于群论，因此这些领域的改进可能会对我们生活的世界的理解和生活方式产生深远的影响。

This project aims to develop new algorithms to aid researchers in computational number theory and other areas of computational Mathematics, Science, and Engineering. Ever since the advent of multi-core desktop computers, there has been a demand for algorithms which are able to take advantage of recent advances in computing technology. Many current algorithms cannot be split apart into multiple parts and run on separate computing cores. Instead the algorithms need to be completely redesigned. Nowhere is this more true than in Computational Number Theory. However many of the basic techniques used in that area of mathematics are similar or the same to those used in other areas of mathematics, etc. For example, fast algorithms for multiplying very large polynomials make use of the Fast Fourier Transform, a technique that is used in signal processing, mathematical modelling and many other areas. In order to facilitate the design of new algorithms, a number of interesting problems in computational number theory have been chosen. The first is to compute large tables of what are known as Hilbert Modular Forms. These mathematical functions have applications to generalisations of the much publicised Fermat's Last Theorem and have links to the theory of elliptic curves, which were used in Andrew Wile's famous proof of the theorem. A second problem is to test a conjecture known as the Vandiver conjecture. This number theoretical conjecture is widely believed to be true, but heuristics suggest we haven't checked it far enough to have any certainty. We can predict roughly how many counterexamples we should have found to date, if any exist, and it is likely less than one. We also know how far to check it to give us a decent chance of finding a counterexample, and this is one of the aims of the project.A third part of the project relates to the security of data transmission, e.g. via the internet and between large corporations. Data is secured and transmitted using mathematical `keys'. In the RSA method of encryption, to decipher such messages, one only needs to factor large numbers into prime factors. The best technique for doing this is the Number Field Sieve. We aim to make use of new techniques in polynomial arithmetic and `sieving' to improve the Number Field Sieve.Another technique which can benefit from improvements in sieving is index calculus, which is used to attack a cryptosystem called the elliptic curve cryptosystem. We aim to apply our knowledge to this problem as well, to ensure that we remain ahead of potential attacks on the security of our personal and financial data. A fourth part of the project involves improving the speed of basic `core' arithmetic computations. A great many researchers and companies rely on certain basic algorithms in polynomial arithmetic and linear algebra to do much of their computational work. Everything from the design of aeroplanes to computer software relies on fast computations which boil down to these basic algorithms. Recent advances of the lead researcher in this project have dramatic implications for numerous basic algorithms. Speeding up such fundamental computations is a specific goal of this project.The final project relates to computing the structure of mathematical objects called groups. Roughly speaking, groups measure symmetries of objects and computing their structure is fundamental to much of mathematics. The specific research to be done will make use of sieving techniques, a la the number field sieve, to improve current algorithms for computing the structure of mathematical groups. Everything from understanding the structure of the universe to codes for securely transmitting data rely on group theory, so improvements in these areas may have profound implications for our understanding and way of life in the world that we live in.