## Product Description

Quantum computational number theory is a new interdisciplinary subject of number theory, computation theory, and quantum computing together. The aim of quantum computational number theory is to use the new quantum computing techniques to solve the intractable computational problems in number theory and numbertheoretic cryptography. Indeed, the most famous quantum algorithm, namely, Shor’s quantum factoring algorithm, is for solving the integer factorization problem and for breaking the RSA cryptographic system.

The book consists of six chapters. In Chapter 1, we try to answer briefly what is computational number theory and what is quantum computational number theory. Chapter 2 presents some basic concepts and results in classical and quantum computation. Chapter 3 gives an account of classical and quantum algorithms for the integer factorization problem (IFP). Chapter 4 discusses classical and quantum algorithms for the discrete logarithm problems (DLP), whereas Chapter 5 deals with classical and quantum algorithms for elliptic curve discrete logarithm problems (ECDLP). Since all classical algorithms are not powerful enough to solve IFP, DLP, and ECDLP in polynomial-time, all IFP-, DLP-, and ECDLP-based cryptographic system is secure, provided that they are constructed and used properly. However, if a practical quantum computer can be built, then the quantum algorithms discussed can be used to break all the IFP-, DLP-, and ECDLP-based cryptographic systems. Of course, we cannot expect quantum algorithms or more generally quantum computers to break all the cryptographic systems, since quantum computers use a different paradigm for computation, and they are not faster version of classical computers; for some computational problems such as IFP and DLP, they can exponentially (more specifically superpolynomially) speed up the computation, but for other problems such as any NP-complete problem, e.g., the traveling salesman problem (TSP), they will not be able to speed up the computation at all. Thus, there exist cryptographic systems that quantum computers cannot break; these types of cryptographic systems are called quantum-resistant cryptographic systems. Finally, in Chapter 6, we shall discuss some more quantum algorithms for other numbertheoretic and algebraic problems.

The monograph can be regarded as a new version of the author’s earlier book Quantum Attacks on Public-Key Cryptosystems, with an emphasis on quantum attacking for both the IFP, DLP, and ECDLP problems and the IFP-, DLP-, and ECDLP-based cryptography. It is self-contained and can be used as a basic reference for computer scientists, mathematicians, electrical engineers, and physicists, interested in quantum computational number theory. It can also be used as an advanced text for final year undergraduates or first-year graduates in the field.

Number theory is one of the oldest subjects in mathematics. Traditionally, number theory is the purest of the pure mathematical discipline. But with the advent of modern computers, it becomes more and more computation involved, giving to the birth of computational number theory, and even the quantum computational number theory, just as analytic number theory and algebraic number theory, where analysis and algebra play an important role. This chapter provides an introduction to the basic ideas and concepts, as well as some important open problems in number theory and computational number theory and quantum computational number theory. More specifically, we shall give a descriptive answer to the following three questions:

1. What is number theory?

2. What is computational number theory?

3. What is quantum computational number theory?