- #1

- 10

- 0

**Frustrating step in a proof -- basic abstract algebra**

Hello all, I am trying to work on a proof related to information theory, and I have gotten stuck. I am nearly 100% this is true, but it might not be . . . and I am having trouble coming up with a proo for it in any case!

----------

M exist in Z_p, and we choose a pair of integers {a,b} also in Z_p, and a != 0. We then calculate E s.t.

E = a*M + b mod p.

Now, here is the ticky part (at least for me). If we consider the pair E and M generated by this function, it's pretty obvious that because of generative nature of mod p we could have chosen a different {a,b} pair and gotten the same solution.

What I am trying to show, is that given all {E,M} pairs, there are

(a) exactly P unique solutions (seems easy, consider the case of a = 1, generate all the solutions by varying b, and then use the birthday property to show that each other solution must map into one of the previously discovered mappings)

and the tricky one . . .

(b) Each E->M mapping possess the same number of solutions in {a,b}

Can anyone nudge me in the right direction? As I said i'm nearly 100% sure that (b) is true because of corrarlies in the affine cryptosystem, but I am having a devil of a time proving it.

Last edited: