Algorithms and Number Theory

This seminar was the third one on number theoretical algorithms at Dagstuhl over the past 7 years. A major goal was always to bring together number theorists who develop the theory for efficient algorithms and people writing the corresponding software for applications. This year we had 42 participants from 13 countries.

In the last few years number theoretical applications to Coding Theory and Cryptography have become more and more important. Hence, it was no surprise that the majority of talks was on topics related to these applications. We would like to mention:

• computations with elliptic curves over finite fields; several new and efficient methods were presented; elliptic curve methods are currently under consideration for becoming part of the new standard for public key cryptosystems;
• primality testing and proving, large primes being of importance for quite a few cryptosystems;
• finite field algorithms, factorization of polynomials over finite fields; the ability to do efficient computations in and with finite fields is a basis for almost all algorithms applied in practice in the areas mentioned; factoring methods for polynomials over finite fields were tremendously improved over the last years;
• class group computations in global fields; since the usefulness of class groups of quadratic number fields for cryptographical applications was demonstrated, this has become a new area of research on a class of basic objects from pure mathematics; as for now the constructive approach is still limited to global fields of small degree.

In the other talks given a large variety of problems in algorithmic (algebraic) number theory was treated as the reader will notice from the subsequent abstracts.

For the organizers it was not easy to squeeze the large number of talks into one week's schedule. Fortunately, most of the talks were short, so that there was still ample time for stimulating discussions. Of course, the special atmosphere of Schloss Dagstuhl also contributed to a very productive meeting.

Reports of the previous seminars on Algorithms and Number Theory are still avail able at Dagstuhl office. Report 39 (22.06.-26.06.92) and 100 (10.10.-14.10.94).