Computational number theory

Project name: Computational number theory (PNA 5.2)

Coordinator of this project: Dr.Ir. H.J.J. te Riele
Startdate: 1997-01-01
Enddate: 2006-12-31

Computational number theory studies problems from elementary, algebraic and analytic number theory which require the help of fast computers, particularly vector and parallel systems. This enlarges our knowledge, insight and understanding in this field and leads to mathematical and numerical solution techniques for the problems studied. Many problems in this field are extremely suitable for parallelization, and can be used as test-cases for high-performance and parallel computing techniques. For example, some algorithms for factoring large numbers can be carried out on a grid of heterogeneous computers where the number of computers in the grid is allowed to vary in a dynamical way.

The emergence of public-key cryptography has particularly triggered the study of algorithms for factorization and primality testing, for computing discrete logarithms, and for the solution of large sparse systems of linear equations over finite fields. These algorithms are studied in this project.

If time and man power permit, additional research efforts will be devoted to problems for which CWI had prior experience. Examples are: the Riemann hypothesis, the Mertens conjecture, the Goldbach conjecture, special number-theoretic (aliquot) sequences and cycles (like amicable numbers), continued fractions of algebraic numbers (click also here), and the systematic computation of multiplicative number-theoretic functions with help of a generalization of the sieve of Eratosthenes.

Recent and current activities are:

Discrete Tomography

This is a joint project with Leiden University (Tijdeman), started on September 1, 2002. Discrete Tomography studies the recovery of binary images from their projections. The purpose of this research is to contribute to the development of the algebraic theory of discrete tomography (DT) and to write computer programs which are based on the developed theory and are aimed at practical applications, e.g. in medical sciences and in crystallography. A first step is to adapt and optimize a DT-program of Hajdu and Tijdeman so that much larger examples can be handled than were possible so far. In addition, the following aspects will be studied: clustered structures, uncertainties at the boundaries of the object, noise in the input data, and the extension of the treatment of 0-1 solutions to the case of an arbitray but finite number of integer solutions. This project has links with the next project (factoring large numbers) namely the handling of large sparse matrices, and the use of parallel computers to solve problems involving such matrices.

Factoring large integers with the Number Field Sieve

This research, jointly with Leiden University (Tijdeman), aims at the algorithmic and implementational improvement of the NFS factoring method. In particular, the generation of proper polynomials used by the siever, the effect of using three large primes in the relations generated by the siever, and the possibility to improve the efficiency of the linear algebra step in NFS will be studied. Boender and Elkenbracht-Huizing have finished their Doctor's Theses in 1997 (on factoring large integers with the Quadratic Sieve and with the Number Field Sieve, respectively) and Cavallar in 2002 (on factoring with the Number Field Sieve).
In this project, regular contributions have been made to the factorization of numbers of world record size. The largest integer factored with a general-purpose algorithm is RSA200 (200 digits), which was factored on May 9, 2005 by Bahr, Boehm, Franke and Kleinjung. [Note: Bahr, Boehm, Franke and Kleinjung factored RSA640 (193 digits) after RSA200.] The previous record was 11²⁸¹+1 (176 digits), which was factored on May 2nd, 2005 by Aoki, Kida, Shimoyama and Ueda. The previous record was RSA-576 (174 digits), which was factored on December 3rd, 2003 into two 87-digit factors using GNFS by Franke, Kleinjung, Montgomery, te Riele, Bahr, Leclair, Leyland, Wackerbarth. A few days later, on December 19th, a 164-digit number was factored by Aoki, Kida, Shimoyama, Sonoda and Ueda. Earlier records have 160 (factored on April 1, 2003), 158 (factored on January 19, 2002), 155, 140, and 130 decimal digits. A variant of NFS called the Special Number Field Sieve (SNFS) is faster than NFS, but only for numbers which can be expressed in a special form like aⁿ+1 or aⁿ-1 where a is a small integer. The current world record for SNFS has 274 decimal digits. It is (6³⁵³-1)/5, factored by Aoki/Kida/Shimoyama/Ueda on January 23, 2006. The previous record was 248 digits, with 2,1642M factored by Aoki/Kida/Shimoyama/Sonoda/Ueda (CRYPTREC) on April 04, 2004. The previous record has 244 decimal digits. It is 2⁸⁰⁹-1, the largest composite Mersenne number with, until it was factored, unknown factors. The previous largest composite Mersenne number with unknown factors is the 227-digit number 2⁷⁵¹-1. It was factored on January 22, 2002. The previous three SNFS records (established on November 14, 2000, on April 8, 1999 and in September 1998) are numbers of 233, 211, and 186 decimal digits, respectively. Since the security of public-key systems like RSA depends on the difficulty of factoring large numbers, these records offer cryptographers a lower bound for the size of a secure public-key in RSA. Workshops on the state-of the-art of factoring large numbers have been organised by CWI in Amsterdam, on June 4, 2002 (talks were presented by Stefania Cavallar, Arjen Lenstra, Thorsten Kleinjung, Jens Franke, Peter Montgomery, and Paul Leyland), and in Utrecht, on December 12, 2003 (talks were presented by Arjen Lenstra, Willi Geiselmann and Rainer Steinwandt, Paul Leyland, Peter Montgomery, Bruce Dodson, Jens Franke, Scott Contini, and Paul Zimmermann).

Computations connected to the Riemann hypothesis and related conjectures

In December 2005, jointly with Tadej Kotnik of the University of Ljubljana, we have started to continue the computations on the Mertens conjecture as published with Andrew Odlyzko in 1985. The first results, with |M(x)|/x^0.5 > 1.218 (where M(x) is the sum of the values of the Moebius function up to and including x), will be presented during the ANTS VII symposium in Berlin, July 23-28, 2006.

Goldbach Conjecture

The Goldbach conjecture has been checked completely up till the bound 10¹⁴ and partially near various powers of ten up till 10³⁰⁰. This result has been applied to reduce the lower bound in the three-primes version of the Goldbach conjecture as studied by Hardy & Littlewood and by Vinogradov. The bound 10¹⁴ has been improved regularly and the current record bound for which the Goldbach conjecture is known to be true, is 3.10¹⁷.

Amicable numbers

The number and the size of known amicable number pairs has grown explosively in recent years: from 1108 amicable pairs in 1972 (the largest pair consisting of two 25-digit numbers), to more than ten million amicable pairs in December 2005 (the largest pair consisting of two 24073-digit numbers). Most results have been obtained in unpublished studies: a survey paper which documents these developments has appeared in the Proceedings of a Conference in Number Theory in Honour of Professor H.C. Williams, held in Banff, Alberta, Canada, May 24-30, 2003 (pp. 179-196 in: Alf van der Poorten and Andreas Stein (eds.), High primes and misdemeanours: Lectures in honour of the 60th birthday of Hugh Cowie Williams, Fields Institute Communications 41, American Mathematical Society, 2004). Here is a bibliography on amicable numbers.