Algorithms for Algebraic Number Theory

该项目旨在开发新的算法，以帮助计算数论和其他计算数学、科学和工程领域的研究人员。自从多核台式计算机出现以来，对能够利用最新计算技术进步的算法的需求就一直存在。许多当前的算法不能被分解成多个部分并在单独的计算核心上运行。相反，算法需要完全重新设计。这在计算数论中是最真实的。然而，该数学领域中使用的许多基本技术与其他数学领域中使用的技术相似或相同。例如，对非常大的多项式进行乘法运算的快速算法利用了快速傅里叶变换，这是一种用于信号处理、数学建模和许多其他领域的技术。为了便于新算法的设计，本文选择了计算数论中一些有趣的问题。第一种是计算被称为希尔伯特模形式的大型表格。这些数学函数可以应用于广为人知的费马大定理的推广，并与椭圆曲线理论有联系，安德鲁·怀尔在著名的定理证明中使用了椭圆曲线理论。第二个问题是检验一个被称为范德福尔猜想的猜想。人们普遍认为这个数字理论猜想是正确的，但启发法表明，我们还没有对其进行足够的验证，无法确定。我们可以粗略地预测到目前为止我们应该找到多少反例，如果有的话，很可能少于一个。我们也知道要检查到什么程度才能给我们找到反例的机会，这也是这个项目的目标之一。该项目的第三部分涉及数据传输的安全性，例如通过互联网和大公司之间的数据传输。数据使用数学“密钥”进行保护和传输。在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.