Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Frustrating step in a proof - basic abstract algebra

  1. Sep 14, 2004 #1


    User Avatar

    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: Sep 14, 2004
  2. jcsd
  3. Sep 14, 2004 #2


    User Avatar

    And this is why we don't do math after 20 hours of no sleep :blushing: Just realized how (b) follows from (a).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook