Función multiplicativa multiplicativa modular en Python

Question

¿Algún módulo Python estándar contiene una función para calcular modular multiplicative inverse de un número, es decir, un número y = invmod(x, p) tal que x*y == 1 (mod p)? Google no parece dar buenos consejos sobre esto.

Por supuesto, uno puede inventar un trazador de líneas de 10 de fabricación casera de extended Euclidean algorithm, pero ¿por qué reinventar la rueda?

Por ejemplo, Java BigInteger tiene modInverse método. ¿Python no tiene algo similar?

Answer 1

Si el módulo es primo (que llaman p), entonces puede simplemente calcular:

y = x**(p-2) mod p # Pseudocode 

O en Python adecuado:

y = pow(x, p-2, p) 

Aquí es alguien que ha implementado algunas capacidades de la teoría de números en Python: http://userpages.umbc.edu/~rcampbel/Computers/Python/numbthy.html

Aquí hay un ejemplo hecho en el indicador:

 
m = 1000000007 
x = 1234567 
y = pow(x,m-2,m) 
y 
989145189L 
x*y 
1221166008548163L 
x*y % m 
1L 

Answer 2

Es posible que también desee ver el módulo gmpy. Es una interfaz entre Python y la biblioteca de precisión múltiple de GMP. gmpy proporciona una función invertido que hace exactamente lo que necesita:

>>> import gmpy 
>>> gmpy.invert(1234567, 1000000007) 
mpz(989145189) 

Actualizado respuesta

Como señaló @hyh, los gmpy.invert() devuelve 0 si no existe la inversa. Eso coincide con el comportamiento de la función mpz_invert() de GMP. gmpy.divm(a, b, m) proporciona una solución general a a=bx (mod m).

>>> gmpy.divm(1, 1234567, 1000000007) 
mpz(989145189) 
>>> gmpy.divm(1, 0, 5) 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
ZeroDivisionError: not invertible 
>>> gmpy.divm(1, 4, 8) 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
ZeroDivisionError: not invertible 
>>> gmpy.divm(1, 4, 9) 
mpz(7) 

divm() devolverá una solución cuando gcd(b,m) == 1 y lanza una excepción cuando no existe el inverso multiplicativo.

Descargo de responsabilidad: Soy el actual mantenedor de la biblioteca gmpy.

actualizada Respuesta 2

gmpy2 ahora plantea adecuadamente una excepción cuando la inversa no existe:

>>> import gmpy2 

>>> gmpy2.invert(0,5) 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
ZeroDivisionError: invert() no inverse exists 

Answer 3

de averiguar el inverso multiplicativo modular le recomiendo usar el extendido de Euclides Algoritmo de la siguiente manera:

def multiplicative_inverse(a, b): 
    origA = a 
    X = 0 
    prevX = 1 
    Y = 1 
    prevY = 0 
    while b != 0: 
     temp = b 
     quotient = a/b 
     b = a%b 
     a = temp 
     temp = X 
     a = prevX - quotient * X 
     prevX = temp 
     temp = Y 
     Y = prevY - quotient * Y 
     prevY = temp 

    return origA + prevY 

Answer 4

Quizás alguien lo encuentre útil (de wikibooks):

def egcd(a, b): 
    if a == 0: 
     return (b, 0, 1) 
    else: 
     g, y, x = egcd(b % a, a) 
     return (g, x - (b // a) * y, y) 

def modinv(a, m): 
    g, x, y = egcd(a, m) 
    if g != 1: 
     raise Exception('modular inverse does not exist') 
    else: 
     return x % m 

Answer 5

Aquí está mi código, podría ser descuidado pero parece funcionar para mí de todos modos.

# a is the number you want the inverse for 
# b is the modulus 

def mod_inverse(a, b): 
    r = -1 
    B = b 
    A = a 
    eq_set = [] 
    full_set = [] 
    mod_set = [] 

    #euclid's algorithm 
    while r!=1 and r!=0: 
     r = b%a 
     q = b//a 
     eq_set = [r, b, a, q*-1] 
     b = a 
     a = r 
     full_set.append(eq_set) 

    for i in range(0, 4): 
     mod_set.append(full_set[-1][i]) 

    mod_set.insert(2, 1) 
    counter = 0 

    #extended euclid's algorithm 
    for i in range(1, len(full_set)): 
     if counter%2 == 0: 
      mod_set[2] = full_set[-1*(i+1)][3]*mod_set[4]+mod_set[2] 
      mod_set[3] = full_set[-1*(i+1)][1] 

     elif counter%2 != 0: 
      mod_set[4] = full_set[-1*(i+1)][3]*mod_set[2]+mod_set[4] 
      mod_set[1] = full_set[-1*(i+1)][1] 

     counter += 1 

    if mod_set[3] == B: 
     return mod_set[2]%B 
    return mod_set[4]%B 

Answer 6

Aquí es una sola línea para CodeFights; es una de las soluciones más cortas:

MMI = lambda A, n,s=1,t=0,N=0: (n < 2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n),-1)[n<1] 

Se volverá -1 si A no tiene inverso multiplicativo en n.

Uso:

MMI(23, 99) # returns 56 
MMI(18, 24) # return -1 

La solución utiliza la Extended Euclidean Algorithm.

Answer 7

Muchos de los enlaces de arriba están rotos en 1/23/2017. encontré esta aplicación: https://courses.csail.mit.edu/6.857/2016/files/ffield.py

Answer 8

Bueno, no tengo una función en Python, pero tengo una función en C que se puede convertir fácilmente a pitón, en el siguiente función c algoritmo de Euclides extendido se utiliza para calcular mod inversa

int imod(int a,int n){ 
int c,i=1; 
while(1){ 
    c = n * i + 1; 
    if(c%a==0){ 
     c = c/a; 
     break; 
    } 
    i++; 
} 
return c;} 

función de Python

def imod(a,n): 
    i=1 
    while True: 
    c = n * i + 1; 
    if(c%a==0): 
     c = c/a 
     break; 
    i = i+1 

    return c 

referencia a la función C anterior es tomada desde el siguiente enlace C program to find Modular Multiplicative Inverse of two Relatively Prime Numbers