What is computational number theory?
Computational number theory, also known as algorithmic number theory is a branch of number theory. It focuses on identifying and using efficient computational methods and algorithms to solve multiple problems in number theory as well as arithmetic geometry.
In recent years, there has been a lot of progress in this sphere, in terms of higher computational speed as well as the identification of increasingly efficient algorithms.
Computational number theory studies whole numbers and, to some extent, even rational and algebraic numbers. It is the study of computations with these types of numbers. Some of the tasks carried out by computational number theorists include:
• Constructing tables that will be used for the purpose of suggesting conjectures about integers.
• Writing programs to test conjectures about integers.
• Writing programs that will be used to prove theorems about integers with several cases.
• Inventing and analyzing algorithms that will be used in the tasks that are listed above.
Computational number theory is used heavily for primality testing as well as the prime factorization of large integers.
It is also used for the purpose of searching for solutions to diophantine equations, and for explicit methods in arithmetic geometry.
Computational number theory is used widely in cryptography. It is used in elliptic curve cryptography, RSA, and post-quantum cryptography. The theory is even used to investigate speculations, notions, and open problems in number theory. It is because of its connections with cryptography that number theory has applications in computer science.
Programs that are used to test a conjecture might either look for a counterexample to disprove the conjecture or verify the conjecture for several cases, thus supporting it. Computer algebra systems employed by scientists and engineers make use of algorithms of number theory to carry out their basic steps.
Quite often, the algorithms used in computational number theory will work exclusively with integers, but this is not always the case. The analysis of such algorithms frequently draws from other areas of mathematics.
Number theory is unique among modern mathematical disciplines because it has whole lot of problems, some of which are extremely hard, that can be stated in terms that are comprehensible to someone who is not a specialist.
What is primality testing?
Primality testing determining whether a number is a prime number or not, without decomposing it into its constituent prime factors. There are two types of primality testing:
- Deterministic primality testing: This gives you an absolutely certain answer about the primality of a number.
- Probabilistic primality testing: Here it is possible (with a minuscule probability) to falsely identify a composite number as a prime number.
Speeding up primality testing is a research topic currently. The majority of fast cryptographic algorithms that need primes tend to pick probable primes due to the fact that probable prime tests are much faster than true prime tests. But real primality tests are speeding up and could soon be fast enough for them to be used in programs like the Secure Sockets Layer.
What is the prime factorization of integers?
Prime factorization is the process of determining the prime factors of a number. This is considered to be a computationally hard problem and there are multiple algorithms with varying levels of sophistication that are used to solve this problem.
Direct search factorization is the simplest way to find the factors. It uses trial division of all possible factors. However, it is only practical for small numbers. Computational number theory is useful for the prime factorization of larger numbers.
What are some of the current research topics in computational number theory?
As we mentioned earlier, faster primality testing is one of the important research topics right now. In addition to this, algorithms for factoring large integers are another major hot topic in computational number theory. The Cunningham Project is one of the benchmarks for the current ability to factor integers. The fastest general factoring algorithm right now is the General Number Field Sieve. It starts by choosing a suitable polynomial that determines how long
the rest of the algorithm will take. You can look at Kleinjung for a good way to select the polynomial and Crandall and Pomerance for a description of the algorithm.
There still is research going on in Diophantine equations (equations with integer coefficients to be solved with integer values for the variables). Many more equations are yet to be solved in whole numbers.
Current work in computational algebraic number theory involves calculations in and regarding
number fields of a degree greater than 2.
Miller and Takloo-Bighash’s book sheds light on some fresh computational work in analytic
number theory, especially on the use of random matrix theory (from physics) to attack the Riemann Hypothesis (a Clay Millennium Problem, is a part of analytic number theory, which employs the analytic methods of calculus and complex analysis to understand the integers.
Recent advances in this field also include the Green-Tao proof that prime numbers do occur in arbitrarily long arithmetic progressions.
What is combinatorial number theory?
Combinatorial number theory is basically combinatorics, seasoned with a few of the algorithmic properties of the integers. It has been referred to as the study of “structured sets of integers” – in contrast with algebraic, analytic, and other areas of number theory, which deal largely with algebraic relations and non-discrete properties of integers.
More than other fields in mathematics, combinatorial number theory is considered to be a recreational field. It is studied lightly, without any real concern for applications. It is encountered quite a lot in the form of problems as well as in classical results.
This subject is interdisciplinary in nature and incorporates ideas from a wide range of different fields including harmonic analysis, graph theory, number theory, ergodic theory, discrete geometry, probability theory, as well as theoretical computer science.
