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".