Algorithms for Algebraic Number Theory

点击翻译按钮获取中文摘要

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.