CODEWITHSUNDEEP
python
iuri
iuri

Reputation: 31

extended euclidean algorithm and the concept of multiplicative inverse

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?

Upvotes: 2

Views: 5412

Answers (2)

Luke Woodward
Luke Woodward

Reputation: 65054

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 262, 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;

Upvotes: 3

Harel
Harel

Reputation: 327

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.

Upvotes: 3

Related Questions