Python Language Exponentiation modulaire: pow () avec 3 arguments


Exemple

Fournir pow() avec 3 arguments pow(a, b, c) évalue l’ exponentiation modulaire a b mod c :

pow(3, 4, 17)   # 13

# equivalent unoptimized expression:
3 ** 4 % 17     # 13

# steps:
3 ** 4          # 81
81 % 17         # 13

Pour les types intégrés utilisant une exponentiation modulaire n'est possible que si:

  • Le premier argument est un int
  • Le second argument est un int >= 0
  • Le troisième argument est un int != 0

Ces restrictions sont également présentes dans python 3.x

Par exemple, on peut utiliser la forme à trois arguments de pow pour définir une fonction inverse modulaire :

def modular_inverse(x, p):
    """Find a such as  a·x ≡ 1 (mod p), assuming p is prime."""
    return pow(x, p-2, p)

[modular_inverse(x, 13) for x in range(1,13)]
# Out: [1, 7, 9, 10, 8, 11, 2, 5, 3, 4, 6, 12]