Numbers with Character

     Number theory is an interesting branch of mathematics that deals with the study and analysis of integers and is primarily done for research or academic purposes. Recreational number theory on the other hand is mostly done by amateurs such as myself for fun and can involve finding patters and solving puzzles using numbers. One can slot number theory into three broad categories. The first being classic or elementary number theory, The second is algebraic number theory and lastly analytic number theory. The List of recreational number theory topics we will discuss herein purely deals with classic number theory.The dutch mathematician Hendrik Lenstra with tounge firmly in cheek stated that "Nowadays, when a Number Theorist applies for a grant, he says that Number Theory is used in cryptography, and so doing Number Theory is good for National Security. Back then, since it was before the discovery of America, they said Number Theory is used in music. But I won't comment on the progress of civilization since then:"

Perfect Numbers

They were most probably first discovered in the time period that spanned the 7th century BC and the 4th century AD by the then Greek speaking world. A perfect number can only be a positive number that equals the sum of its divisors, excluding itself. In the first examples listed the integer 6 is not only divisible by 1, 2 and 3 but the sum of 1,2 & 3 is also equal to 6.

6 = 1+2+3

28 = 1+2+4+7+14

496 = 1+2+4+8+16+31+62+124+248

Narcissistic Numbers

Greek mythology states that Narcissus who was the son of river god Cephissus and nymph Liriope was a person of exceptional beauty. Narcissus ended up dying because he was unable to leave a pool after falling in love with his own reflection. we also happen to have numbers that can’t get enough of themselves. They happen to be numbers that are the sum of its own digits when each digit is raised to the power of the number of digits. By that definition all one digit numbers are narcissistic. There are no two digit narcissistic numbers but there are four three-digit narcissistic numbers.

370 = 3^3 + 7^3 + 0^3

1^3 + 5^3 + 3^3

1^3 + 5^3 + 3^3

Mersenne Primes

Marin Mersenne who "Mersenne Primes" were named after is a very interesting individual. Mersenne was an ordained priest and a friar who while in Paris at the convent of the annunciation met other greats like René Descartes and Étienne Pascal (father of Blaise Pascal) who influenced his work. Mersenne also seemed to be a man of strong convictions who was an ardent supporter of Galileo during the geocentric vs heliocentric debates even though he was a Catholic. Mersenne primes are prime numbers that fit the pattern 2^p-1, where p is any prime number. An example is where p=2, therefore 2^2-1 = 3. Three happens to be a prime hence it is a Mersenne prime. Other Mersenne primes include

p = 3, therefore 2^3-1 = 7

p = 5, therefore 2^5-1 = 31

p = 7, therefore 2^7-1 = 127

p = 11, therefore 2^11-1 = 2047

Dudeney Primes

Henry Dudeney was an English civil servant who at a very young age was much inspired by his grandfather who was also a mathematician. He was considered one of Englands premiere recreational number theorists and puzzle maker. Dudeney noticed that some  numbers exhibit a behavior where the numbers individual digits sum add up to their cube root. There are only six known Dudeney numbers until someone proves this wrong.

1) number 1  where, 1 = 1, and 1*1*1 = 1

2) number 512  where, 5+1+2 = 8, and 8*8*8 = 512

3) number 4913 where 4+9+1+3 = 17 and 17*17*17 = 4913

4) number 5832 where 5+8+3+2 = 18 and 18*18*18 = 5832

5) number 17576 where 1+7+5+7+6 = 26 and 26*26*26 = 17576

6) number 19683 where 1+9+6+8+3 = 27 and 27*27*27 = 19683

Twin, Cousin & Sexy Primes

I first heard about twin, cousin and sexy primes while watching an episode of the "Colbert Report" when they had on Terence Tao the mathematical genius from Caltech. Twin primes are when the difference between two consecutive primes is equal to two. Examples of twin primes are:

(3,5) (5,7) (11,13) (17,19) (29,31)

Cousin primes are when the difference between two consecutive primes is equal to four. Examples of cousin primes are:

(3, 7), (7, 11), (13, 17), (19, 23), (37, 41)

Finally Sexy primes are when the difference between two primes is equal to (you guessed it) six:

(5,11), (7,13), (11,17), (13,19), (17,23)

     The recreational number theory topics listed above are the ones that intrigued me and more importantly the ones that I could understand. If this is something you like, you can lookup a fairly exhaustive list of topics listed on wiki which can be found here (https://goo.gl/OVVH0m). 

The Magic of Primes in PKI

     Almost all of us that live in an internet enabled world have used PKI (Public Key Infrastructure) in some form or fashion. If you work in the information technology field, more specifically on the security side of the house, you would have definitely heard of PKI. Every time we use email, do our online banking or connect to our offices networks using VPN we could possibly be using PKI. The PKI framework itself is so pervasive and robust that it is abstracted from the general user community. In the bargain we have forgotten that it evens exists or bother to think about how it works.

     From a high level perspective it is fairly easy to understand how PKI functions. It is essentially a two key (asymmetric) encryption system that provides authentication and confidentiality. Lets assume two users (Andy and Bob) want to communicate securely over a public network where transmitted data can by spied upon easily. To prevent the spying Andy can encrypt the message he sends to Bob using key X. The issue we now have is that if Andy encrypted the data using key X, how does he send the key to Bob to decrypt it without it being compromised. This problem is what the PKI framework solves. It does this by generating two keys per user (a public key and a private key) that are mathematically linked to each other. The public key as its name implies is public and can be shared with others. Now if Andy needs to communicate with Bob he requests the public key for Bob. Once Andy receives the key he encrypts the message and sends it to Bob. This message can only be decrypted using Bob's private key which never leaves his person. A hacker that compromised the encrypted message and Bob's public key will never be able to decrypt Andy's message leaving him rather perplexed.

     Lets take a look at the actual math behind PKI, because that is where it gets really interesting. Before we do that, we have to understand that PKI is a framework and not a technology implementation, therefore I am going to show you how the RSA algorithm that implements the PKI framework functions. The public key is actually made up of two parts. One is a composite of two primes (two primes multiplied by each other) which you will see below referenced as k1 and the second is an exponent which will be referenced as e. This is a special exponent that needs to fulfill the following requirements. The exponent needs to be an integer. The exponent cannot be a factor of k1. In addition it needs to be greater than 1 but less than φ(k1). What exactly is φ(k1) you ask ? It is all the numbers that are less than k1 but greater than 1 and do not share a common factor with k1.  It all sounds too complicated but lets take a look at φ(9) as an example.

1. Lets list out all the numbers that are lesser or equal to 9 = (1,2,3,4,5,6,7,8)
2. Now we will mark in red all the numbers that share a factor with 9 except for the number 1 and erase them (1,2,3,4,5,6,7,8)
3. We are now left with 6 numbers (1,2,4,5,7,8 ) 
4. So the φ(9) =  6

Step 1 - Generate Public Key

To generate a public key we pick two large primes and multiply them together to form a composite. For this example we will pick small primes so that it becomes easier to work with.

• k1 = PrA x PrB
• k1 = 23 x 29
• k1 = 667

Lets also pick an exponent that meets the requirements such that 1 < e < φ(k1). For this example I am going to pick  the number 3. What we are left with is two numbers k1 = 667 and e = 3. These two numbers together make up the public key.

Step 2 - Generate Private Key

• k2 = 2(φ(k1))+1 / e
• k2 = 2(φ(667))+1 / 3
• k2 = 2(616)+1 / 3
• k2 = 1232+1 / 3
• k2 = 1233 / 3
• k2 = 411

Remember that k2 is the private key that is never distributed to anyone, It is only used to decrypt messages that are sent to you which is encrypted by k1 and e which together make up your public key.

Step 3 - Data Encryption

Now that we have both a public and private key we can begin to encrypt data. We will attempt to encrypt the word "bag" as an example. Firstly we need to convert the word "bag" to some sort of numerical value so that we can do calculations against it. The easiest way to do this is to find the numerical place value of the letters. For example "b" will have a value of 2 as it is the second letter in the English alphabet. By that logic the word bag = 217. Now we can begin the encryption process.

• ed = data^e mod k1
• ed = 217^3 mod 667
• ed = 10218313 mod 667
• ed = 540

Step 4 - Data Decryption

If you are attempting to do this on a calculator even with the fairly small numbers that I have shown here the calculations are going to be huge. I am including a link for a big integer calculator here which will help you make these calculations (http://goo.gl/GXSdCv)

• dd = ed^k2 mod k1
• dd = 540^411 mod 667
• dd= 10323697896242668219954362115926597275247250862687291172394408598235646340560963277503503134090563294398280979796545134818573213064741511000526138653105369880225616050484894381599128674424417000626405170045975711797996349495340567543681315349755878142749780282862273187818683269529600679603730315376728985279076969364683520463773650596665685647638324598792650556617337357191019481317184045352277937331907517838610430973762375649970512352333359870591860750640525281545205463597201920722441526847683758018612285502996206303677486482364237501952886563083240964158025078640998912337940214285221812259921170151592015645065351114155483987914299497389946764598690494890769755112018882602072423747515993913989410381103104000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 mod 667
• dd = 217

Our decrypted message is 217. If we pass his through our letter place value calculation we will come up with the word "bag". 

Sieve of Eratosthenes (Part 2)

Eratosthenes

    Eratosthenes was by all accounts a polymath and probably the first recorded one in history. He was a close friend of Archimedes (of the Eureka fame) who also shared his love of Mathematics. Eratosthenes list of achievements is truly impressive. He was a mathematician, geographer, poet, astronomer, music theorist, the inventor of geography and the chief librarian at the ancient Library of Alexandria. While Eratosthenes worked at the library, a more modern theoretical physicist named Albert Einstein worked at the patent office. This allowed them to be exposed to many different ideas from various perspectives. This I believe is one of the critical reasons as to why both Einstein and Eratosthenes were so far ahead of their times.

    I am just going to focus on one of his achievements, which is a sieve used to find consecutive prime numbers that was named after him. Eratosthenes was a Greek citizen born in 276 BC in Shahhat, Libya and eventually died in 194 BC in his much beloved Alexandria, Egypt. After loosing his vision he suffered a bout of depression, leading him to voluntarily starve himself to death at the age of 82.  The reason it is important to keep these dates in perspective is because the next sieve to find primes was invented in 1934 by S. P. Sundaram, an Indian student 2128 years later. The one after that was invented in 2004 by Arthur Oliver Lonsdale Atkin a British mathematician 70 years later. Given the time that Eratosthenes lived in and the resources available to him, you can appreciate the sheer magnitude of his discovery. Although now there are so many faster ways to find large primes like "Fermat little theorem" or the "Sieve of Atken", Eratosthenes's sieve was used well into the 21st century, for cryptography and other purposes. 

    My simple python script to find primes turned into a history lesson which I thought is important to share. Learning is the act of acquiring by synthesizing different types of information. Not only were Einstein and Eratosthenes exposed to different ideas,  they wanted to learn by exploring the unknown. Today with the democratization of technology, and the penetration of the internet almost all information is a google search away. You are only bound by your willingness to learn. Keep your eyes open, find what you love to do and explore away. 

Sieve of Eratosthenes (Part 1)

    In an attempt to grasp the fundamentals of python, I decided to give myself a challenge. The challenge was to find prime numbers between 1 and x. The idea here was that while attempting to find these primes, I would end up learning about loops, conditional statements, breaks, e.t.c. I finished the challenge, but ended up learning a lot more than just the fundamentals of python.

    I started off with the brute force method. This method looped through a set of numbers one at a time, and then made sure that only 1 mod the current number and the current number mod itself had a remainder of 0. If so it was a prime number. Imagine looping though a set of numbers 1 to x, where x was greater than or equal to 1,000,000. You will quickly realise that although this method worked it had obvious flaws. It was inefficient and time consuming. To speed up the process I started storing the primes in memory as I kept finding them. Then I started looping through the found primes and doing a modulus with the current number. This reduced the number of modulo operations I had to do, but it was still fairly time consuming.

    I needed to find yet a faster method to find primes and came across a simple but elegant method called the "Sieve of Eratosthenes". Eratosthenes used a process of elimination until you were only left with primes. His method is summed up below. 

1. Create a list of consecutive numbers from 1 to x and cross out 1 because it is not a prime number.
2. Start with the next number p which is 2 in this case and circle it. Next eliminate all multiples of p (eg:- 4,6,8,e.t.c.)
3. p takes on the value of the next number in the list and repeat step 2
4. Keep going until p multiplied by p is greater than or equal to x

Sieve of Eratosthenes

    This was much quicker and could be implemented writing a lot less code. This got me interested in Eratosthenes and I wanted to know more about him. (Continued in Part 2 .... )