Complex Hard Computational Problems in Number Theory

The textbook examines in detail the four problems that have attracted researchers’ attention in the past few decades: prime factorization of large composite numbers, computation of discrete logarithms in the multiplicative residue group by a prime modulus, the solution of large sparse systems of linear equations over finite fields, the computation of the rank of elliptic curves defined over field of rational numbers. The fastest algorithms for solving the first two problems are based on what is known to be a numerical field sieve algorithm that reduces them to the solution of large sparse systems of linear equations over finite fields. These systems are so large that conventional solution algorithms are not applicable to them. Special block iterative algorithms are used instead. This area of the applied number theory is now being actively developed around the world due to its application in cryptography. Because of the absence of lower complexity estimates for solving these number-theoretic problems, the only way to verify the reliability of the cryptographic algorithms used is by running a practical test involving most advanced algorithms and most powerful computers.