Dados dos números positivos xy ncon x<2^n, escriba la función más corta posible para calcular x^-1 mod 2^n. En otras palabras, encuentre ytal que x*y=1 mod 2^n.

Su función debe completarse en un tiempo razonable al menos n=64, por lo que una búsqueda exhaustiva no funcionará.

Si el inverso no existe, debe indicarlo al llamador de alguna manera (lanzar una excepción, devolver un valor centinela, etc.).

Si se pregunta por dónde comenzar, pruebe el Algoritmo Euclidiano Extendido .

Python 95 89

ces tu funcion Devuelve 0 si no hay inverso (es decir, cuando x es par).

p=lambda x,y,m:y and p(x,y/2,m)**2*x**(y&1)%m or 1
c=lambda x,n:[0,p(x,2**n-1,2**n)][x%2]

Python, 29 bytes

lambda x,n:pow(x,2**n-1,2**n)

Esto devuelve 0 para incluso x . Utiliza el teorema de Euler, con la observación de que 2 ^ n - 1 es divisible por 2 ^ ( n - 1) - 1, a través de la exponenciación modular rápida incorporada de Python. Esto es lo suficientemente rápido para n hasta 7000 más o menos, donde comienza a tomar más de aproximadamente un segundo.

Mathematica - 22

f=PowerMod[#,-1,2^#2]&

f[x,n]vuelve ycon x*y=1 mod 2^n, de lo contrariox is not invertible modulo 2^n

GolfScript (23 caracteres)

{:^((1${\.**2^?%}+*}:f;

El resultado centinela para un inverso inexistente es 0 .

Esta es una aplicación simple del teorema de Euler . , entonces x - 1 ≡ x 2 n - 1 - $x^{\varphi(2^n)} \equiv 1 \pmod {2^n}$$x^{-1} \equiv x^{2^{n-1}-1} \pmod {2^n}$

Desafortunadamente, es un exponencial demasiado grande para calcular directamente, por lo que tenemos que usar un bucle y hacer una reducción modular dentro del bucle. El paso iterativo es y tenemos una opción de caso base: ya sea con$x^{2^k-1} = \left(x^{2^{k-1}-1}\right)^2 \times x$k=1

{1\:^(@{\.**2^?%}+*}:f;

o k=2con

{:^((1${\.**2^?%}+*}:f;

Estoy trabajando en otro enfoque, pero el centinela es más difícil.

La observación clave es que podemos construir el inverso hacia arriba poco a poco: si $xy \equiv 1 \pmod{2^{k-1}}$$xy \in \{ 1, 1 + 2^{k-1} \} \pmod{2^k}$$x$$x(y + xy-1) \equiv 1 \pmod{2^k}$$y' = (x+1)y - 1$

$0x \equiv 1 \pmod {2^0}$

$x\left(\frac{1 - (x+1)^n}{x}\right) \equiv 1 \pmod {2^n}$

$x+1$ es par.

Eso le da la función de 19 caracteres

{1$)1$?@/~)2@?%}:f;

$x$x&11

{1$.1&+1$?@/~)2@?%}:f;

$0$$2^{n-1}$ , pero aún no lo he probado.

$0$$1 - (x+1)^n$$1 - 1^n$

{1$.1&*)1$?@/~)2@?%}:f;

$n$n x f

{..1&*)2$?\/~)2@?%}:f;

Ruby - 88 caracteres

Usa la función f.

def e a,b;a%b==0?[0,1]:(x,y=e(b,a%b);[y,x-(y*(a/b))])end
def f x,n;e(x,2**n)[0]*(x%2)end

Simplemente la función recursiva de la página wiki vinculada, devuelve 0 en caso de error.

Haskell, 42 bytes

_!1=1
x!n|r<-x!div(n+1)2=(2-r*x)*r`mod`2^n

Usando un algoritmo basado en el lema de Hensel que duplica el número de dígitos en cada iteración, ¡esto se ejecuta en menos de un segundo por n hasta aproximadamente 30 millones !

Pyth , 9 bytes

.^Et^2Q^2

Pruébalo aquí!

Toma la entrada en orden inverso. O, 9 bytes demasiado: .^EtK^2QK.

Explicación

. ^ Et ^ 2Q ^ 2 - Programa completo.

^ - Función Pow. Lo mismo en Python (pow).
  E - La segunda entrada.
    ^ 2Q - Y 2 ^ primera entrada.
   t - Disminuido.
       ^ 2 - Y 2 ^ primera entrada de nuevo.

GAP, 39 bytes

f:=function(x,n)return 1/x mod 2^n;end;

f(x,n)devuelve el inverso del xmódulo 2^ny muestra un mensaje de error

Error, ModRat: for <r>/<s> mod <n>, <s>/gcd(<r>,<s>) and <n> must be coprime

si no existe inversa