What Number Theory Is Actually About

Chapter 1 of Computational Number Theory and Modern Cryptography is orientation week. Song Y. Yan, ISBN 978-1-118-18858-3, starts with integers. Not apps. Not HTTPS. Integers. I rolled my eyes, then I remembered this 2013 Wiley book is trying to show why those integers are the internet’s load-bearing walls.

Sections 1.1 and 1.2 ask two questions. What is number theory? What is computation theory? The first one is the pretty puzzles. The second one is the rude follow-up. Can a machine solve those puzzles in time you would wait for?

Integers, then the three bins

Number theory, in Yan’s first sentence, is mainly about properties of the integers. Especially positive integers. Divisibility is the opening act.

Every positive integer falls into one of three bins. The unit is 1. Primes are 2, 3, 5, 7, and so on. Composites are 4, 6, 8, 9, and so on. A prime greater than 1 has only 1 and itself as divisors. Everything else composite is built from primes. And 1 is neither prime nor composite. Yan just states it and moves.

Then the load-bearing theorem. Any integer n greater than 1 can be written uniquely as a product of primes, with the primes in order and exponents positive. Unique factorization. If you have ever wondered why RSA even has a chance, this is the cultural background. Primes are atoms. The product is the molecule. Going forward is easy. Going backward is the whole industry.

Euclid, density, and a million-dollar zero

Euclid already proved there are infinitely many primes. The sequence does not stop. Yan writes that as π(x) going to infinity as x goes to infinity, where π(x) counts primes up to x. He even dumps a table. At 10 to the 15 you already have about 29 trillion primes. At 10 to the 24 the count has 23 digits. There is no shortage of atoms.

The book’s snapshot of “largest prime” is dated. Yan says it was 2^43112609 - 1, found on 23 August 2008, with 12,978,189 digits. Records moved. The point did not. We keep finding bigger ones because the list never ends.

The Prime Number Theorem is the density rule. π(x) is about x over log x, natural log, base e. In the limit, that ratio goes to 1. Primes get thinner as numbers get bigger, in a controlled way. A slow fade you can write as a formula.

If the Riemann Hypothesis is true, you get a sharper error term. Of course, he says, we do not know if it is true. RH is one of the seven Millennium Prize Problems from the Clay Mathematics Institute in 2000. One million US dollars. The zeta function is the sum of 1 over n^s, with s a complex number. The hypothesis says every nontrivial zero in the critical strip sits on the line where the real part is 1/2. Riemann computed the first five and they all sat there. Then he guessed the rest do too.

I have watched people treat RH like a crypto bug. It is not. It is a statement about how regularly primes appear. RH would tidy the error terms. It would not, by itself, hand you a factoring algorithm.

Twin primes, Goldbach, and a Fields Medal

Then the unsolved neighborhood. Twin primes are pairs like n-1 and n+1, both prime. (3, 5), (5, 7), (11, 13). Yan’s largest pair in the table is 65516468355 times 2^333333, plus or minus 1, found in August 2009, both with 100,355 digits. The twin prime conjecture says there are infinitely many. We still do not have that theorem.

Chen showed there are infinitely many pairs (n, n+2) where n is prime and n+2 has at most two prime factors. Close. Not twins. Goldbach’s conjecture, from a 1742 letter to Euler, says every even number greater than 4 is the sum of two odd primes. Chen’s best hit is that every sufficiently large even number is a prime plus a product of at most two primes.

RH, twins, and Goldbach make Hilbert’s 8th problem. Green and Tao proved in 2007 there are arbitrarily long arithmetic progressions of primes. Tao got a Fields Medal in 2006. Yan’s punchline is the one I keep repeating. Problems in number theory are easy to state and often very hard to solve.

Then he asks what a computer even is

Section 1.2 is the mood shift. Computation theory asks whether problems can be solved on a model of computation, and how efficiently. Two branches. Computability: what a computer can do with no resource cap. Complexity: what it can do with time or space limits. Feasibility is the sub-plot crypto actually cares about. Polynomial time. Practical. Not “in theory after the heat death of the universe.”

The model is the Turing machine, from Alan Turing in 1936. Finite states, tapes, a head that reads and writes. Deterministic if the next step is unique. Nondeterministic if it can branch. Probabilistic if some states toss a fair coin.

Church-Turing says any effectively computable function can be computed by a Turing machine. Crypto people mostly do not live on that line. We live on the next one. Cook-Karp. Any computationally tractable problem can be computed by a Turing machine in deterministic polynomial time. “Can it halt?” is computability. “Can it halt before I die?” is complexity.

P, NP, and the word hard

P is the class of problems solvable in polynomial time on a deterministic Turing machine. Addition of two integers, no matter how big, is in P. Yan calls P tractable, feasible, easy.

NP is solvable in polynomial time on a nondeterministic machine. In language terms, P is decide-in-poly-time. NP is verify-in-poly-time. The Traveling Salesman Problem is his NP example. He also introduces NP-complete, NP-hard, EXP, and the randomized classes RP, ZPP, and BPP. I am not reprinting the state diagrams.

Here is where I got annoyed, then grateful. In the definition block, Yan classifies NP problems as intractable and hard. That is sloppy if you already know P sits inside NP. Two pages later he says P versus NP is one of the greatest unsolved problems in computer science and mathematics. Another Clay million-dollar problem. So he knows. The early “NP means hard” line is a teaching shortcut.

Cook-Karp is the cultural rule. Problems in P are tractable. Problems not in P are not. There is no clean cut, because maybe P equals NP. Yan is honest about the inclusions we do know. PSPACE equals NPSPACE. P is properly inside EXP. Most of the other sandwich might or might not be strict.

The thought I could not shake

Crypto people casually say “hard.” Factoring is hard. Discrete log is hard. Yan’s chapter 1 will use those words too. But already in 1.2 he is setting a trap for his later self, and I think he knows it.

Polynomial time is the working definition of practical. If you have a poly-time algorithm, the problem is “easy” in this book’s dialect. If you do not, we call it hard. That is a complexity slogan, not a theorem about integers.

He has not proved factoring is outside P. He has not proved discrete log is NP-complete. Section 1.2 is full of problems that are complete for NP, like SAT and TSP, and a separate pile of number problems we only believe are nasty. That distinction is the whole security model, hiding in a definitions section.

Number theory gives you infinite primes and unique factorization. Computation theory gives you a stopwatch and a dare. Yan is careful enough to say we have not proved the one-wayness. Next he names the maps.

Previous: Why Computational Number Theory Still Runs the Internet Next: Computation Theory and Why Hard Problems Matter