Frustrating step in a proof - basic abstract algebra

  • Thread starter Chu
  • Start date
  • #1
Chu
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:

Answers and Replies

  • #2
Chu
10
0
And this is why we don't do math after 20 hours of no sleep :blushing: Just realized how (b) follows from (a).
 

Related Threads on Frustrating step in a proof - basic abstract algebra

  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
7
Views
5K
Replies
2
Views
2K
Replies
5
Views
2K
  • Last Post
Replies
5
Views
945
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
7
Views
5K
  • Last Post
Replies
9
Views
4K
  • Last Post
Replies
21
Views
7K
Top