extended euclidean algorithm and the concept of multiplicative inverse

Question

I have with python:

e*d == 1%etf

we know (e) and (etf) and must discover (d) using the extended euclidean algorithm and the concept of multiplicative inverse of modular arithmetic.

d = (1/e)%etf

d = (e**-1)%etf

generate a global wrong number, please help me find (d) using the rules above explained.

The solution (Modular multiplicative inverse function in Python) illustrated below gives me wrong computational result

e*d == 1 (mod etf)
d = (e**(etf-2)) % etf 
d = pow(e,etf-2,etf)

Am I making some mistake elsewhere? Is this calculation ok?

I gave an implementation of the extended Euclidean algorithm in an answer to a separate question: http://stackoverflow.com/a/11703184 — Luke Woodward, Sep 20 '12 at 19:30
Well @woodward in a firt look inward your function I see only 1 parameter of input. To calculate d I suppose is necessary know the variables etf and e, since the problem is ( d*e == 1 % etf ). — iuri, Sep 21 '12 at 19:27

score 3 · Answer 1 · answered Sep 20 '12 at 19:30

3

The trick you list with d = (e**(etf-2)) % etf will work only if etf is prime. If it's not, you have to use the EEA itself to find the modular multiplicative inverse.

answered Sep 20 '12 at 19:30

Harel

327
1
5

score 3 · Answer 2 · edited May 23 '17 at 12:27

Here's an implementation of the extended Euclidean algorithm. I've taken the code from this answer, generalised it so that it works with moduli other than 2⁶², and converted it from Java to Python:

def multiplicativeInverse(x, modulus):
    if modulus <= 0:
       raise ValueError("modulus must be positive")

    a = abs(x)
    b = modulus
    sign = -1 if x < 0 else 1

    c1 = 1
    d1 = 0
    c2 = 0
    d2 = 1

    # Loop invariants:
    # c1 * abs(x) + d1 * modulus = a
    # c2 * abs(x) + d2 * modulus = b 

    while b > 0:
        q = a / b
        r = a % b
        # r = a - qb.

        c3 = c1 - q*c2
        d3 = d1 - q*d2

        # Now c3 * abs(x) + d3 * modulus = r, with 0 <= r < b.

        c1 = c2
        d1 = d2
        c2 = c3
        d2 = d3
        a = b
        b = r

    if a != 1:
        raise ValueError("gcd of %d and %d is %d, so %d has no "
                         "multiplicative inverse modulo %d"
                         % (x, modulus, a, x, modulus))

    return c1 * sign;

extended euclidean algorithm and the concept of multiplicative inverse

2 Answers2

Linked

Related