99 cents:  50 25 10 10 1 1 1 1

1,5,10,25,50



Number-theoretic Algorithms

We will work our way up to RSA Encryption.

public key encryption.

ABCDEFGHIJKLMNOPQRSTUVWXYZ
BCDEFGHIJKLMNOPQRSTUVWXYZA

MY DOG HAS FLEAS

NZ EPH IBT GMFBT

1.  The most common letter in the alphabet is E.  So, the most common in your encrypted is almost always E.

2.  The most common three-letter sequence in English is THE.  So, now that you where the E's are, look for the XYE pattern; you'll find one of these a lot.  That gives you the T and the H.

3.  Now that you know the E's T's and H's, you can just play Wheel of Fortune on the rest of it.

So, computer encryption is a cipher, but over MUCH larger sets than 26.

RSA encryption was the first algorithm where the key could be made public.  So, ANYONE can send a message to me, but ONLY I can decrypt it.  I've made my key public, but even with you knowing that key, you can't figure out the decrypt key.

There are fast algorithms for determining whether a large number is prime.  (These are called "probable prime" algorithms; they don't always work, but they can get the right answer, like, 99.999% of the time.)

So, if you want a 100-digit prime.  Generate 100 random digits, test if it's prime.  If it's not, try again.  Primes are not rare; you'll find one soon.

The RSA algorithm is based around the product of two very large primes.  The public key is essentially, two large primes multiplied together, like, two 100-digit primes multiplied together to get a 200-digit prime.

The only known way to compute the decrypt value is to factor that 200-digit number into its component primes.  Unfortunately, the fastest known way to factor is trial and error (dividing the number by primes up to the square root).

Factor 1027  = 13x79

pow(a,b)%c

c|a*b

Fast algorithms for pow(a,b)%c where a,b,and c can be very large.  Note:  do NOT multiply a by itself b times and then mod c at the end.  DON'T.


13 raised to 14  mod 11  pow(13,14)%11


13%11=2       14
4%11 =4        7
16%11=5        3
25%11=3        1   <= STOP AT 1

So, I look at the rows where the exponent is odd.   4, 5, 3.  I multiply these:  (4x5)%11 = 20%11 = 9.  (9*3)%11 = 27%11 = 5.

pow(13,14)%11 = 5


2 = 13^1 %11
4 = 13^2 %11
5 = 13^4 %11
3 = 13^8 %11

13^2 * 13^4 * 13^8 = 13^14  (when you multiply you add exponents).

(4*5*3)%11 = 13^14  %11.


14(base 2) = 1110. = 2^3 + 2^2 + 2^1
                     13^8 * 13^4 * 13^2 = 13^14.