Inverso multiplicativo modular

22

Su tarea es dar dos números enteros ay bcalcular el inverso multiplicativo modular de un módulo b, si existe.

El inverso modular del amódulo bes un número ctal que ac ≡ 1 (mod b). Este número es un módulo único bpara cualquier par de ay b. Existe solo si el máximo común divisor de ay bes 1.

La página de Wikipedia para el inverso multiplicativo modular se puede consultar si necesita más información sobre el tema.

Entrada y salida

La entrada se da como dos enteros o como una lista de dos enteros. Su programa debe generar un solo número, el inverso multiplicativo modular que se encuentra en el intervalo 0 < c < bo un valor que indique que no hay inverso. El valor puede ser cualquier cosa, excepto un número en el rango (0,b), y también puede ser una excepción. Sin embargo, el valor debe ser el mismo para los casos en los que no hay inversa.

0 < a < b se puede suponer

Reglas

  • El programa debe finalizar en algún momento y debe resolver cada caso de prueba en menos de 60 segundos.
  • Se aplican lagunas estándar

Casos de prueba

Los casos de prueba a continuación se dan en el formato, a, b -> output

1, 2 -> 1
3, 6 -> Does not exist
7, 87 -> 25
25, 87 -> 7
2, 91 -> 46
13, 91 -> Does not exist
19, 1212393831 -> 701912218
31, 73714876143 -> 45180085378
3, 73714876143 -> Does not exist

Tanteo

Este es el código de golf, por lo que gana el código más corto para cada idioma.

Esta y esta son preguntas similares, pero ambas solicitan situaciones específicas.

Halvard Hummel
fuente
66
Del pequeño teorema de Fermat se deduce que el inverso multiplicativo de a, si existe, puede calcularse eficientemente como a ^ (phi (b) -1) mod b, donde phi es la función totient de Euler: phi (p0 ^ k0 * p1 ^ k1 * ...) = (p0-1) * p0 ^ (k0-1) * (p1-1) * p1 ^ (k1-1) * ... Sin decir que conduce a un código más corto :)
ngn
1
@Jenny_mathy Por lo general, no se permite tomar entradas adicionales.
Sr. Xcoder
3
Cuento seis respuestas que parecen ser de fuerza bruta, y es poco probable que ejecute todos los casos de prueba en 60 segundos (algunos de ellos dan un error de memoria o de pila primero).
Ørjan Johansen
1
@ngn: Has combinado el pequeño teorema de Fermat (FLT) con la mejora de Euler. Fermat no sabía sobre la función phi de Euler. Además, la mejora de FLT y Euler solo se aplica si gcd (a, b) = 1. Finalmente, en la forma en que lo ha escrito, "a ^ (\ phi (b) -1) mod b" es congruente con 1, no un ^ (- 1). Para obtener un ^ (- 1), use a ^ (\ phi (b) -2) mod b.
Eric Towers
1
@EricTowers Euler es una consecuencia. Con respecto a "mcd (a, b) = 1", dije "si existe [lo contrario]". ¿Estás seguro de phi (b) -2?
ngn

Respuestas:

11

Mathematica, 14 bytes

Obligatorio Mathematica incorporado :

ModularInverse

Es una función que toma dos argumentos ( ay b), y devuelve el inverso de un mod b si existe. Si no, devuelve el error ModularInverse: a is not invertible modulo b..

Tutleman
fuente
7

JavaScript (ES6), 79 73 62 61 bytes

Devuelve falsesi el inverso no existe.

Utiliza el algoritmo Euclidiano extendido y resuelve todos los casos de prueba casi al instante.

f=(a,b,c=!(n=b),d=1)=>a?f(b%a,a,d,c-(b-b%a)/a*d):b<2&&(c+n)%n

Casos de prueba

Arnauld
fuente
¿Por qué no es posible escribir el nombre de la función f, como en f (c, a, b = 0, d = 1, n = a) => c? F (a% c, c, d, b- ( aa% c) / c * d, n): a <2 && (b + n)% n?
RosLuP
@RosLup f(x,y)siempre se analiza como una llamada de función, excepto si está precedido explícitamente por la functionpalabra clave. Una función de flecha anónima, por otro lado, se declara como (x,y)=>somethingy f=(x,y)=>somethingasigna la función a la fvariable.
Arnauld
4

Jalea , 2 bytes

æi

Pruébalo en línea!

Esto utiliza un builtin para el inverso modular, y devuelve 0 para ningún inverso modular.

Jalea , 7 bytes

R×%⁸’¬T

Pruébalo en línea!

Emite un conjunto vacío (representado como una cadena vacía) en ningún inverso modular. Se queda sin memoria en TIO para los casos de prueba más grandes, pero debería funcionar con suficiente memoria.

Cómo funciona

R×%⁸’¬T  
R        Generate range of b
 ×       Multiply each by a
  %⁸     Mod each by b
    ’    Decrement (Map 1 to 0 and all else to truthy)
     ¬   Logical NOT
      T  Get the index of the truthy element.

Si desea trabajar para casos de prueba más grandes, intente esta versión (relativamente sin golf), que requiere mucho tiempo en lugar de memoria:

Jalea, 9 bytes

×⁴%³’¬ø1#

Pruébalo en línea!

Cómo funciona

×⁴%³’¬ø1#
        #   Get the first
      ø1      one integer
            which meets:
×⁴            When multiplied by a
  %³          And modulo-d by b
    ’         Decrement
     ¬        Is falsy
fireflame241
fuente
4

Python 2 , 34 bytes

f=lambda a,b:a==1or-~b*f(-b%a,a)/a

Pruébalo en línea!

Función recursiva que da Trueporprint f(1,2) que yo creo que es aceptable, y los errores de entradas no válidas.

Estamos tratando de encontrar x en ax1(modb) .

ax1=kbk

Tomando moda1kb(moda)kb1(moda)k

kF(-si%una,una)

unaunasi

kunaX-1=ksiXksi+1una

Kritixi Lithos
fuente
3

Números R + , 15 bytes

numbers::modinv

vuelve NApara aquellos asin inversos mod b.

R-Fiddle para probarlo!

R , 33 bytes (no competitivos)

Esto fallará en muy grande bya que en realidad crea un vector de 32*bbits de tamaño .

function(a,b)which((1:b*a)%%b==1)

Pruébalo en línea!

Devuelve integer(0)(una lista vacía) para aquellos asin mod inverso b.

Giuseppe
fuente
3

Mathematica, 18 bytes

PowerMod[#,-1,#2]&

input

[31, 73714876143]

J42161217
fuente
3

Python 2 , 51 49 54 53 51 49 bytes

-1 byte gracias a officialaimm
-1 byte gracias a Shaggy

a,b=input()
i=a<2
while(a*i%b-1)*b%a:i+=1
print+i

Pruébalo en línea!

Imprime 0cuando no hay solución.

Rod
fuente
1
Outputs 0 for a=1 and b=2; from the test cases, it should output 1.
Shaggy
As a recursive algo
Mr. Xcoder
1
As Shaggy pointed out, fails for 2, 1
Mr. Xcoder
@Shaggy should work now
Rod
This fails to return an answer in 60 seconds (on TIO) for the input 31,73714876143.
Ilmari Karonen
3

Japt, 9 8 bytes

Takes the inputs in reverse order. Outputs -1 for no match. Craps out as the bigger integer gets larger.

Ç*V%UÃb1

Test it

  • Saved 1 byte thanks to ETH pointing out an errant, and very obvious, space.
Shaggy
fuente
The test input 73714876143,31 seems to produce an out-of-memory error on Firefox (and to crash Chromium). I don't think this is a valid answer.
Ilmari Karonen
@IlmariKaronen: I clearly pointed out that fact in my solution. We can assume infinite memory for the purposes of code golf so the memory issues and crashes do not invalidate this solution.
Shaggy
1
Unfortunately the memory issues also make it impossible to tell whether your code would actually solve the test cases in 60 seconds as stipulated by the challenge. I suspect it would not, even if there was sufficient memory available to make it not crash, but without a computer that can actually run the program for that long there's no way to tell for sure.
Ilmari Karonen
2

Python 3 + gmpy, 23 bytes

I don't think it can get any shorter in Python.

gmpy.invert
import gmpy

Try it online! (won't work if you do not have gmpy installed)

Mr. Xcoder
fuente
2

Python 3, 49 bytes

lambda a,b:[c for c in range(b)if-~c*a%b==1][0]+1

Try it online!

Python 3, 50 bytes

lambda a,b:[c for c in range(1,b+1)if c*a%b==1][0]

Try it online!

This throws IndexError: list index out of range in case there is no modular multiplicative inverse, as it is allowed by the rules.

Mr. Xcoder
fuente
This fails to return a result for the input 31,73714876143 in 60 seconds (on TIO).
Ilmari Karonen
@IlmariKaronen parece terminar en 56 segundos en mi máquina (Macbook Pro '15)
Sr. Xcoder
2

8 , 6 bytes

Código

invmod

Explicación

invmodes una octava palabra que calcula el valor de la inversa de a, módulo b. Vuelve nullen desbordamiento u otros errores.

Uso y casos de prueba

ok> 1 2 invmod .
1
ok> 3 6 invmod .
null
ok> 7 87 invmod .
25
ok> 25 87 invmod .
7
ok> 2 91 invmod .
46
ok> 13 91 invmod .
null
ok> 19 1212393831 invmod .
701912218
ok> 31 73714876143 invmod .
45180085378
ok> 3 73714876143 invmod .
null
Chaos Manor
fuente
2

J , 28 bytes

4 :'(1=x+.y)*x y&|@^<:5 p:y'

Pruébalo en línea!

Utiliza el teorema de Euler . Devuelve 0 si el inverso no existe.

Explicación

4 :'(1=x+.y)*x y&|@^<:5 p:y'  Input: a (LHS), b (RHS)
4 :'                       '  Define an explicit dyad - this is to use the special
                              form `m&|@^` to perform modular exponentiation
                          y   Get b
                      5 p:    Euler totient
                    <:        Decrement
             x                Get a
                   ^          Exponentiate
               y&|@             Modulo b
       x+.y                   GCD of a and b
     1=                       Equals 1
            *                 Multiply
millas
fuente
2

Pyth , 10 bytes

3 bytes guardados gracias a @Jakube .

xm%*szdQQ1

Pruébalo aquí!

Devoluciones -1 para no inversa multiplicativa.

Desglose de código

xm%*szdQQ1      Let Q be the first input.
 m      Q       This maps over [0 ... Q) with a variable d.
   *szd         Now d is multiplied by the evaluated second input.
  %    Q        Now the remained modulo Q is retrieved.
x        1      Then, the first index of 1 is retrieved from that mapping.

Pyth , 15 13 bytes

KEhfq1%*QTKSK

Lanza una excepción en caso de que no exista inverso multiplicativo.

Pruébalo aquí!

Pyth , 15 bytes

Iq1iQKEfq1%*QTK

Esto agrega muchos bytes para manejar el caso donde no existe dicho número. El programa puede acortarse significativamente si no fuera necesario manejar ese caso:

fq1%*QTK

Pruébalo aquí!

Sr. Xcoder
fuente
2 bytes guardados conKExm%*QdKK1
Jakube
O 3 bytes si intercambia el orden de las entradas:xm%*szdQQ1
Jakube
@Jakube Muchas gracias, editando!
Sr. Xcoder
¿Como funciona esto?
Kritixi Lithos
@Cowsquack He agregado un desglose de código completamente primitivo, pero no tengo tiempo para incluir una explicación completa. Espero que sea lo suficientemente claro por ahora, pero intentaré agregar una explicación más completa pronto.
Sr. Xcoder
1

C (gcc) , 115 bytes

#define L long long
L g(L a,L b,L c,L d){return a?g(b%a,a,d-b/a*c,c):b-1?0:d;}L f(L a,L b){return(g(a,b,1,0)+b)%b;}

Pruébalo en línea!

Algoritmo euclidiano extendido, versión recursiva

C (gcc) , 119 bytes

long long f(a,b,c,d,t,n)long long a,b,c,d,t,n;{for(c=1,d=0,n=b;a;a=t)t=d-b/a*c,d=c,c=t,t=b%a,b=a;return b-1?0:(d+n)%n;}

Pruébalo en línea!

Algoritmo euclidiano extendido, versión iterativa

nwellnhof
fuente
1

C (gcc) , 48 110 104 bytes

#define f(a,b)g(a,b,!b,1,b)
long g(a,b,c,d,n)long a,b,c,d,n;{a=a?g(b%a,a,d,c-(b-b%a)/a*d):!--b*(c+n)%n;}

Pruébalo en línea!

Esto debería funcionar con todas las entradas (que caben dentro de un largo) en 60 segundos.

Editar. Ya estoy abusando de la nvariable, así que podría suponer que gcc pone la primera asignación %rax.

techo
fuente
1
Por desgracia, esto da resultados incorrectos incluso para entradas bastante pequeñas debido al desbordamiento de enteros dentro del bucle. Por ejemplo, f(3,1000001)devuelve 717, lo que obviamente no tiene sentido (la respuesta correcta es 333334). Además, incluso si este error se solucionó utilizando un tipo entero más amplio, este enfoque de fuerza bruta sin duda agotaría el tiempo para algunos de los casos de prueba más grandes dados en el desafío.
Ilmari Karonen
0

Axioma, 45 bytes

f(x:PI,y:PI):NNI==(gcd(x,y)=1=>invmod(x,y);0)

0 por error, de lo contrario, devuelva z con x * z Mod y = 1

RosLuP
fuente
0

Python 2 , 52 bytes

-3 bytes gracias al Sr. Xcoder.

f=lambda a,b,i=1:i*a%b==1and i or i<b and f(a,b,i+1)

Pruébalo en línea!

Salidas Falsesin solución y errores a medida que baumenta.

TIO integrado

Solo estoy probando iframes en Stack Snippets y funcionan absolutamente fantástico.

totalmente humano
fuente
No estoy seguro de que esto funcione, ¿no puede i*a%bser 0?
Wheat Wizard
Falla con el error "profundidad de recursión máxima excedida" para la entrada (31,73714876143).
Ilmari Karonen
0

JavaScript (ES6), 42 41 39 38 bytes

Salidas falsepara ninguna coincidencia. Lanzará un error de desbordamiento cuando el segundo número sea demasiado grande.

x=>y=>(g=z=>x*z%y==1?z:z<y&&g(++z))(1)
Lanudo
fuente
0

Jalea , 27 bytes

²%³
⁴Ç⁹Сx⁸
ÆṪ’BṚçL$P%³×gỊ¥

Pruébalo en línea!

Utiliza el teorema de Euler con exponenciación modular. Como Jelly no tiene un generador incorporado para realizar la exponenciación modular, tuvo que implementarse y tomó la mayoría de los bytes.

millas
fuente
0

Axioma, 99 bytes

w(a,b,x,u)==(a=0=>(b*b=1=>b*x;0);w(b rem a,a,u,x-u*(b quo a)));h(a,b)==(b=0=>0;(b+w(a,b,0,1))rem b)

usa la función h (); h (a, b) devuelve 0 si el error [no existe inverso] de lo contrario, devuelve la z tal que a * z mod b = 1 Esto estaría bien incluso si los argumentos son negativos ...

esta sería la función general egcd () que retunr una lista de int (por lo que también pueden ser negativos)

egcd(aa:INT,bb:INT):List INT==
   x:=u:=-1   -- because the type is INT
   (a,b,x,u):=(aa,bb,0,1)
   repeat
      a=0=>break
      (q,r):=(b quo a, b rem a)
      (b,a,x,u):=(a,r,u,x-u*q)
   [b,x, (b-x*aa)quo bb]

así es como lo usas

(7) -> h(31,73714876143)
   (7)  45180085378
                                                    Type: PositiveInteger

Encuentro la base algo en internet desde https://pastebin.com/A13ybryc

RosLuP
fuente