Part one introduced Fermat and his “Last” and “Little” Theorems. Part two showed the preliminary steps for creating an uncrackable* code. We picked two different primes, **p** and **q**, a whole number **e** smaller than **pq **(aka **n**), which has no factors in common with (**p**-1)(**q**-1) and a whole number **d** with the property that **de** has remainder 1 when divided by (**p**-1)(**q**-1). We released **n** and **e** to the world and kept **d**, **p** and **q** private.

* Not a guarantee! ðŸ˜‰

**Recap
p** = 37 and

**q**= 41 in our example. They would be much, much bigger in practice.

**pq**=

**n**= 1517. This is the first half of the

*public*key.

(

**p**-1)(

**q**-1) = 1440.

**e**= 7. No factors in common with 1440. This is the second half of the

*public*key.

**d**= 823.

**de**= 5761 which gives 4 remainder 1 when divided by 1440.

**d**is the

*private*key.

Also, to speed things up when discussing remainders, instead of saying “7 has remainder 2 when divided by 5” we can say 7 is equal to 2, modulo 5 or 7 = 2 mod 5.

Fermatâ€™s Little Theorem

Ifpis any prime number andais any whole number thatpdoesnâ€™t divide evenly (i.e. without a remainder) then, if you raiseato the power ofp-1 and then divide byp, you get a remainder of 1 no matter what exact numbersaandpare.

In our new notation,a^(p-1) = 1 modp.

**Encrypting
**Alice takes her message M and converts it to a number

**m**(known as the

*plaintext*), using some agreed technique, e.g. A = 01, B = 02, etc…

She raises

**m**to the power of

**e**(the public key), then divides by

**n**and takes the remainder,

**c**. This is the

*ciphertext*that Alice sends to Bob.

**m**^

**e**=

**c**mod

**n**.

Do try this at homeUsing the numbers in our example, try turning “MY” into a secret message. Answers at the bottom of this post. You will need the cunning technique given at the end of this post to help you in the calculations.

**Decrypting**

Bob takes **c** and raises it to the power of **d** (the private key) and divides by **n**. The remainder he gets will mathemagically be equal to **m**, the plaintext Alice encrypted. He converts back to text, e.g. 01 = A, 02 = B, etc… and reads the message. **c**^**d** = **m** mod **n**.

Do try this at home 2Using the numbers in our example, try cracking the secret message “238”.

**Why it Works?**

So no doubt you’re wondering how it all works. Why does the original number pop out no matter what? Well, it goes a little something like this…

The Long Version

c^d= (m^e)^dmodn=m^demodn.

Recall thatde= 1 mod (p-1)(q-1) by design. Sode= 1 mod (p-1) andde= 1 mod (q-1).

Hence, there are two whole numbers, call themaandb, such that;

de=a(p-1) + 1

de=b(q-1) + 1.

Fermat’s Little Theoremsaysm^(p-1) = 1 modp, sincepis prime.*

Hence,m^de=m^(a(p-1)+1) =m*(m^(p-1))^a=m*(1^a) modp. Som^de=mmodp.

Also,m^de=m^(b(q-1)+1) =m*(m^(q-1))^b=m*(1^b) modq. Som^de=mmodq.

Sincepandqare two distinct primesm^de=mmodpq=mmodn.* Strictly speaking FLT is only true if

pdoesn’t dividembut if it does then it dividesm^deas well som^de=m(=0) modpanyway.

**The Short Version**

Raise **c** to the power of **d**, divide by **n** and take the remainder. Fermat’s Little Theorem and some other cunning mathsy manipulations guarantee you’ll get **m**, the original message as your answer.

**Cunning Technique for Raising to Big Powers While Taking Remainders under Division so as to Avoid Melting Your Calculator
**If

**x**=

**a**mod

**n**, then there is some whole number

**b**such that

**x**=

**bn**+

**a**. So

**x**^2 = (

**bn**+

**a**)^2 = (

**bn**)^2 + 2

**abn**+

**a**^2. Since (

**bn**)^2 and 2

**abn**are both divisible by

**n**, the remainder of

**x**^2 is the same as the remainder of

**a**^2 when divided by

**n**.

**Example:** Say we want to know the remainder of 7^8 when dividing by 9.

7^2 = 49. 49 = 4 mod 5.

7^4 = (7^2)^2 = 4^2 mod 5 = 16 mod 5 = 1 mod 5.

7^8 = (7^4)^2 = 1^2 mod 5 = 1 mod 5 since squaring 1 just gives 1.

**Quick Check:** 7^8 = 5764801 which gives 1152960 when you divide by 5 and a remainder, conveniently enough, of 1.

Answers to Puzzles“MY” encrypts to 928. Decoding 238 yields 1415, which reads “NO”.

Loving this! I’m one of those people who likes hard maths in a kind of casual way where I can’t really do it for myself but enjoy someone who knows what they’re talking about telling me about it, this is great! Do more mathsy things Eoghan! Mags

By:

Margueriteon August 16, 2008at 1:21 pm

Like Margeurite, I like all this stuff and like my Catholicism, I’m a non practioner.

I went to see Simon Singh speak in the RDS a couple of years ago and he was brilliant, though he didn’t mention Fermat.

Lar

By:

Laron August 18, 2008at 6:18 pm

[…] – bookmarked by 6 members originally found by brightideasguru on 2008-09-14 Fermatâ€™s Fermaths 3 https://casacaseycourtney.wordpress.com/2008/08/14/fermats-fermaths-3/ – bookmarked by 6 members […]

By:

Bookmarks about Fermaton October 5, 2008at 11:30 pm