1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Extended Euclidean Algorithm Explanation Help and Modular Multiplicative Inverse

Discussion in 'C' started by Peter_APIIT, Mar 29, 2009.

  1. Peter_APIIT

    Peter_APIIT New Member

    Joined:
    Apr 11, 2007
    Messages:
    92
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Student
    Location:
    Malaysia
    Hello to all, i have a hard time understand this these two topics.

    I hope someone can clear my myth.

    I do check the EEA page and did quite amount of research regarding this topic.

    This is what i understand.

    51x + 36y = gcd(a, b)
    Rewrite them in quotient remainder theorem

    Euclid Algorithm
    51 = 1 x 36 + 15 52 / 36 = 3 r 6
    36 = 2 x 15 + 6 36 / 15 = 2 r 6
    15 = 2 x 6 + 3 15 / 6 = 2 r 3
    6 = 2 x 3 + 0 6 / 2 = 3 r 0

    Extended Euclidean Algorithm
    =Take the last second solution

    15 = 2 x 6 + 3
    Rewrite the remainder at LHS

    3 = 15 - 2 x 6
    = 15 - 2 x (36 - 2 * 15)
    = 5 * 15 - 2 * 36 (simplifying)(*)
    = 5 * (51 - 36) - 2 * 36
    = 5 * 51 - 7 * 36 (simplifying)(*)

    Question
    1. How modular multiplicative inverse related to EEA ?
    Please show example.
    2. How to simplify the equation(*) ?
    3. How human hand calculation differ to code implementation ?

    Thanks for your help.
     

Share This Page