algorithme euclidien étendu et concept d'inverse multiplicatif

Question

Je l'ai fait avec Python :

e*d == 1%etf

nous connaissons (e) et (etf) et nous devons découvrir (d) en utilisant l algorithme euclidien étendu et le concept de inverse multiplicatif de l'arithmétique modulaire.

d = (1/e)%etf

d = (e**-1)%etf

générer un faux numéro global, aidez-moi à le trouver. (d) en utilisant les règles expliquées ci-dessus.

La solution ( Fonction inverse multiplicative modulaire en Python ) illustré ci-dessous me donne un résultat de calcul erroné

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

Est-ce que je fais une erreur ailleurs ? Ce calcul est-il correct ?

Answer 1

L'astuce que vous listez avec d = (e**(etf-2)) % etf ne fonctionnera que si le etf est premier. S'il ne l'est pas, vous devez utiliser l'EEE lui-même pour trouver l'inverse multiplicatif modulaire.

Answer 2

Voici une mise en œuvre de l'algorithme euclidien étendu. J'ai pris le code de cette réponse et l'a généralisé pour qu'il fonctionne avec des modules autres que 2. 62 et l'a converti de Java en 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;