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

Homework Help: Multiplicative Inverse. Affine Cipher

  1. Sep 13, 2008 #1

    cks

    User Avatar

    Here is how to find the a^(-1)

    According to the definition,

    aa^(-1)=1mod (26)

    For example, let’s try a=3

    According to Extended Euclidean Algorithm

    gcd⁡(a,26)=gcd⁡(3,26)=gcd⁡(3,2)=gcd⁡(1,2)
    Where
    1=3-1*2
    2=26-8*3
    1=3-1*(26-8*3)=-1*26+9*3

    With 9 found,
    a^(-1)=9

    However, to find a=5
    gcd⁡(5,26)=gcd⁡(5,1)
    1=1*26-5*5

    So,a^(-1)=-5???

    (-5)(5)=1mod(26) which is correct

    How to get a^(-1) in this case as shown in the table which is 15?
     
  2. jcsd
  3. Sep 16, 2008 #2

    cks

    User Avatar

    I manage to solve the problems. Never mind. Thank you.
     
  4. Sep 17, 2008 #3

    HallsofIvy

    User Avatar
    Science Advisor

    5-1 (mod 26) is NOT 15. 5*15= 75= 2*26+ 23. 5*16= 23 (mod 26), not 1.

    5-1 (mod 26)= 26+ (-5)= 21. 5*21= 105= 4*26+ 1. 5*21= 1 (mod 26).

    -5= 21 (mod 26).
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook