1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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
    Staff Emeritus
    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).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Multiplicative Inverse. Affine Cipher
  1. Affine Space (Replies: 2)

Loading...