Joshua Holden

Made it all the way through section 1.5!

It's not a textbook, but it is a great deal more rigorous than your usual popular math book. It's a difficult middle ground and it sometimes fails to deliver.

I really only read the elementary stuff, about the Caesar cypher and affine cyphers. The basic idea is that there is an algorithm which is a simple formula, as:

P = C = K = {0, ..., N}.
p in P, p is a code for a plaintext character
c in C, c is a code for a encrypted character
k in K, k is the encryption key

the generalization of the Caesar cypher yields the following algorithm:
(I) c = p + k mod N + 1

Note that this is a surjective mapping for any k in K. To decrypt:
p = c + (N + 1 - k) mod N + 1. So, N + 1 - k is the additive inverse of k in this modular arithmetic. Note that 0 is the identity here.

Using multiplication instead of addition and changing things slightly:
P = C = {1, ..., N}.

(II) c = p * m mod N

GCD(m, N) = 1.

Example: N = 25, m = 3; N = 8, m = 3

The inverse of m under this relation can be discovered by noticing that if the GCD is 1, then writing out each equation that is yielded by executing the GCD algorithm will yield a series of equation, which with substitution, will give an equation with the form 1 = x * m + y * N. x is the inverse.

Example:

a) 8 = 2 * 3 + 2
b) 3 = 2 * 1 + 1
c) 2 = 1 * 2 + 0

(c) isn't interesting, but (b) and (a) can be rearranged like this:

b') 1 = 3 - 2 * 1
a') 2 = 8 - 2 * 3

Substituting into b':
1 = 3 - (8 - 2 *3) * 1
gathering up the 8's and 3's:
1 = 3 - (8 - 2 * 3)
1 = 3 * 3 - 8
so we can conclude that 3 inverse is 3 here.… (mehr)