Number Theory for Programmers, Part 1
What is Number Theory?
Number theory is the study of numbers, their properties, and what can be inferred from their properties. For programmers, it is most practical to focus on the theory of positive integers.
Who should use this guide?
Those who did not know the answer to the above question.
How do we use modulus?
First, we should bridge the gap between a Programmer’s definition of modulus and a Mathematician’s.
Programmer: a % b is the remainder of a / b. Essentially, the programmer uses the following equation:
That is, the programmer says If we were finding 23 % 5, we would have:
% 
.
Mathematician: Mathematicians rearrange the above equation into the following:
. They write this as:
All this means is that you can move from a to r just by adding and subtracting b.
23 – 5 – 5 – 5 – 5 = 3, so 
Efficient Exponentiation (mod n)
Let’s say that you need to find 
. The naive way of doing this is to perform the operation just as it’s written:
unsigned int powmod(unsigned int a, unsigned int x, unsigned int n) { return pow(a, x) % n; }
and it has a few disadvantages.
- It has a very good chance of overflowing native data types
- It has an algorithmic complexity of O(n) for the size of the exponent. For large integer types, this becomes O(nm), for integers of (on average) mwords
To show a more efficient way of doing it, we will use a method called “successive squaring”. I will explain it by using an example: Find 
:
We know that 
. We need to find 
:
. This is given.
.
This is where the leap of logic occurs. Since 
, it follows that 
So 
% 5 = 3, and I was able to do it all in my head! For small numbers, this is usually the case. But it should be obvious that this is a lot easier than ordinary exponentiation, with on the order of O(logn) multiplications.
Code example
The best code example I have found is from Bruce Schneier’s “Applied Cryptography”. The C version using native unsigned integers is as follows:
unsigned int powmod(unsigned int base, unsigned int exp, unsigned int mod) { unsigned int toret=1; while(exp > 0) { if(exp & 1) toret = (toret * base) % mod; exp >>= 1; base=(base*base) % mod; } return toret; }
It’ll still overflow for the wrong values, but it is a quick and dirty example. If you have access to an infinite precision integer, it should be trivial to convert it.
Fermat’s Little Theorem
One of the many things that Fermat conjectured (and supposedly proved) is quite useful to the modern programmer. It says, for any prime number p, and for any integer a
.
Combined with the successive squaring method, this provides us a very powerful tool.
Probabilistic Primality Testing
For any number of applications, we need prime numbers. They are the crack-cocaine of modern mathematics. There are many simple ways to get prime numbers, such as the Sieve of Eratosthenes, but these methods fail when your application needs a 20-digit prime. There are newly developed (but complicated) tests that give a definite yes/no on a number in polynomial time, but they require Abstract Algebra, which is beyond the scope of this entry! For most developers, we don’t need to be 100% sure the numbers we are using are prime. We’re not using RSA in life-or-death (or multi-billion dollar banking) situations! All we want to do is tell whether or not an integer is most likely prime so that we can encrypt our Dawson’s Creek fan fiction and hide it from our father.
Fermat’s Little Theorem is always true if we know that the modulus is prime. The proof, however, doesn’t hold true in the opposite direction: if, for some number a, 
, we can’t say for sure that n is a prime. However, it is very frequently true, and often enough that we can form a probabilistic test, meaning that the numbers are probably prime. Mathematicians are noted for devastating understatement, so when we say “probably”, we mean “the chance is absurdly close to 100%”. According to pgp.net, PGP uses trial division for primes less than 8191, and the Fermat test for 2,3,5, and 7. I can’t find a reliable source covering the mathematics of why, but an unreliable source gives the chance that a composite is picked as less than 1 in 
. Yikes!
The Test
Ready?
For some number n, it is probably prime if:
If this makes you uncomfortable by using the first two primes, you can randomly pick two numbers (instead of 2 and 3). The test works just the same. For the ultra paranoid, try it three or four times.
The Carmichael Numbers
There are numbers that cause this test to fail for all test values. They are called Carmichael numbers, named after the first person to find an example. The first three are 561, 1105, and 1729. There are infinitely many Carmichael numbers, though they grow more scarce as the integers approach infinity. For fun, use the method of successive squaring to show that 561 is a Carmichael number.
Popularity: 72% [?]
Reader Comments
Can you expand a bit on the notation you are using, please? In particular the triple equals and the way of writing the modulus:
(assuming == is your three-bar-equals)
23 % 5 == 3
is rearranged to:
23 == 3 (mod 5)
But isn’t this a different equation? Instead of saying “the remainder of dividing twenty three by five is three”, the way you have introduced says “twenty three is one of the numbers in the form 5n+3″.
So it changes from:
23 % 5 = 3
to
5n + 3 (can equal) 23
(and why is there no plus in there? as in, 23 == 3 + (mod 5))
Does “(mod 5)” mean “5n where n is any positive integer”?
Also, in the following line:
3^4 == (3^2)^2 == 4^2 == 16 == 1(mod 5)
how/why/where does the step (3^2)^2 == 4^2 come from?
I apologize for my lack of explanation of the modulus. A mathematician views the modulus as defining a “Complete Residue System”. The least-positive “residues” (mod 5) would be 0, 1, 2, 3, 4. Each of those numbers are considered “Congruence Classes”. 3 and 23 are in the same congruence class (mod 5) exactly because they are both of the form 5n+3, as you noticed.
The reason that there is no plus in there is based on usage. A programmer uses the modulus for the purpose of calculating something. The mathematician uses the modulus for the reason of stating something that is already true. 9 % 7 is a problem a programmer might face, and s/he would get 2 as an answer. The mathematician, seeing that 2 and 9 are separated by 7, would then write 2 == 9 (mod 7), as that is a fact, as both of them are in the congruence class 2.
As for why 3^2 == 4, look at the line above it. It shows that 3^2 == 9 == 4(mod 5).
I think your effort to elucidate this topic is nice.
However, your use of the modulus operator without properly defining the mechanics behind it is not only bound to confuse your readers. It is also not proper mathematically speaking.
Specifically, you need to define the rules of the modulus operator (triple equal) and establish what is and isn’t allowed by manually showing the additions etc… You are using it very much like an equal sign, where an equal sign has in its definition that if a = b and b = c, then a = c. That *is* what equal is defined as.
Congruence is another beast altogether… So you cannot simply power the two sides of a triple equal and posit that the statement still holds.
Aside from the fundamental rigor involved in this, I think it’s of vital importance to *really* understand what’s going on. Not just have a “note from the Math department” saying that it holds true.
Just to be clear: the step before “this is where the leap of logic occurs” is unproven.
3^2 t= 9 t= 4 mod 5
(3^2)^2 t= 4^2 is wrong. Why should it? You have to prove this using induction or something else. That’s kind of the whole point of the proof. All else is simply application.
Note: I use t= for triple equal, or congruent.
me:
I agree, but I didn’t write the article “Number Theory for Mathematicians”. I’m playing loose and fast with the rules intentionally, because I feel the results of Number Theory are more interesting for the intended audience. I personally feel the opposite, so I make it my business to know why. If I took the time to properly define addition and multiplication and show when division is valid, my audience would have gone somewhere else. I’m trying to show interesting results that come via Number Theory, and how they’ve crept into my Computer Science education.
And transitivity is, in fact, valid for congruences of positive numbers, as they are all numbers of the form an + b (mod n). I didn’t “power the two sides of the triple”, I powered one side, and then showed what it was equal to. I was reducing a statement, not solving an equation. The error, of course, is on my side for not being clear.
Not to mention you can exponentiate both sides of a congruence and get the same answer. One of the properties of congruences is:
if a==b(mod n), and c==d(mod n), then ac == bd (mod n).
Letting c be a, and b be d, we get aa == bb (mod n). Rinse and repeat for desired power.
me:
It is simply because of substitution. 3^2 and 4 are in the same congruence class, as shown in the above step. In the step in question, I’m only substituting two numbers that are in the same congruence class. I don’t need to prove anything, because they are the same as far as the congruence is concerned. You can substitute any number just the same. We work with the least positive residues because it’s convenient, but the math works out the same.
I’m not really sure what other proof you’d like to see, other than if a t= b (mod n), then ca t= cb (mod n), but that proof is easy enough that one can just work it out on his or her own to satisfy him or herself.
I guess. I don’t think having this line would scare people away:
“I leave it to the reader to prove that “if a==b(mod n), and c==d(mod n), then ac == bd (mod n) and hence a^2 == b^2(mod n)”
Anyways, good article.
Ok, I will respond but from purely an academic and didactic perspective… Take it as constructive criticism, I’m not trying to be annoying.
Take this example: define cosh x = (e^x – e^-x) / 2
The fact that we’ve called it cosh in no way gives it any inherent meaning. In fact, it has nothing to do with trigonometric functions. It’s not even periodic. So for that matter, we might as well call it f(x) = (e^x – e^-x) / 2, and g(x) = (e^x + e^-x) / 2
Now, we see that f(x)^2 + g(x)^2 = 1. By *analogy* we then call them cosh and sinh. But this again, doesn’t grant them any more powers… We still have to one by one go and prove each statment a-la g’(x) = f(x) by manually deriving each exponential, and only after we’ve established that all the trig statements work with sinh and cosh can we now take those properties for granted.
In the same way, your saying that they are congruent classes is all fine and dandy, but the operation you do right here:
3^2 == 4 (mod 5)
(3^2)^2 == 4^2 (mod 5)
is just wrong. Wrong not in that it’s the wrong answer, it’s wrong in that it’s not a proof. You’ve just used two analogous looking things (like sinh and sin) and asserted they behave the same way. The implicit line I’ve added in there is the equivalent sign. That equivalence is simply not trivial.
The verbose proof would be:
“3^2 == 4 (mod 5)
(3^2) * (3^2) == 4 * 4 (mod 5) since a==b(mod n) and c==d(mod n) => ac == bd (mod n)
(and I will leave it to the reader to establish that…)”
You’re just making it look too much like an equal sign, and I’m ready to bet lots of money that many people just assumed it behaved like an equal sign without any foundation.
Why go into the math at all then? just use standard library functions.
Point taken. Thank you for your feedback
I’ll try to be a little more precise in future posts
i took a brief course on number theory in high school. As a programmer who has learned little about c, I found this to be an excellent example of the usefulness of bitwise functions when making large calculations. Through college, i never found any use for the “&” function and it was lost in my c++ vocabulary. I had to look it up to make sure i understood what it was doing. Throughout my college, i had only used the logical “&&.”
Thanks for showing us these great tricks when dealing with math that involves the power of 2. Heck, i hadn’t even realized that bitwise ANDING of any number with 1 will only produce 0 when the number is a power of two. You made me dig deep to understand what “if(exp & 1)” actually mean’t. And in it, i learned what bitwise anding was for.
Thankyou so much, you are a powerful mathematician and an experienced programmer.
With this and “Elementary Theory of Numbers” by William J. LeVeque (Dover Books on Advanced Mathematics) people are on their way.
Pshaw to those who say you need more background. It does not have to be a Journal paper. It is enough to get people off their keister’s and look up the notation, should take about 30 seconds. People unfamiliar but interested in the topic should take some initiative.
As they say in the textbooks: “It is left to the student to…”.
http://en.wikipedia.org/wiki/Number_theory
“unsigned int powmod(unsigned int a, unsigned int x, unsigned int x)”
You have two ‘x”s which have the same type. I guess the second one should be ‘n’.
Michael writes: “Heck, i hadn’t even realized that bitwise ANDING of any number with 1 will only produce 0 when the number is a power of two.”
That is incorrect. It will produce 0 any time the number is even.
I have a question…in proving that there are infinitely many primes congruent to 4 (mod 5), i’m at a loss for understanding the concept by using A = 5* p1, p2…..pr +4 (Begining with 19)
I’m not sure how to explain what goes wrong