Dados dois números positivos xe ncom x<2^n, escreva a função mais curta possível para calcular x^-1 mod 2^n. Em outras palavras, encontre ytais que x*y=1 mod 2^n.

Sua função deve ser concluída em um tempo razoável, pelo menos n=64, para que a pesquisa exaustiva não funcione.

Se o inverso não existir, você deve indicar isso ao chamador de alguma forma (lançar uma exceção, retornar um valor de sentinela, etc.).

Se você está se perguntando por onde começar, tente o Algoritmo Euclidiano Estendido .

Python 95 89

cé a sua função. Retorna 0 se não houver inverso (ou seja, quando x é 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)

Isso retorna 0 para x mesmo . Ele usa o teorema de Euler, com a observação de que 2 ^ n - 1 é divisível por 2 ^ ( n - 1) - 1, através da exponenciação modular rápida embutida no Python. Isso é rápido o suficiente para n até 7000, aproximadamente, onde começa a demorar mais de um segundo.

Mathematica - 22

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

f[x,n]retorna ycom x*y=1 mod 2^n, caso contráriox is not invertible modulo 2^n

GolfScript (23 caracteres)

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

O resultado sentinela para um inverso inexistente é 0.

Esta é uma aplicação simples do teorema de Euler . , entãox - 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}$

Infelizmente, é um exponencial grande demais para calcular diretamente, portanto, precisamos usar um loop e fazer uma redução modular dentro do loop. A etapa iterativa é e temos uma opção de caso base: ou com$x^{2^k-1} = \left(x^{2^{k-1}-1}\right)^2 \times x$k=1

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

ou k=2com

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

Estou trabalhando em outra abordagem, mas o sentinela é mais difícil.

A principal observação é que podemos construir a inversa pouco a pouco: se então , e se é ímpar, temos . (Se você não estiver convencido, verifique os dois casos separadamente). Portanto, podemos começar em qualquer caso base adequado e aplicar a transformação um número adequado de vezes.x y ∈ { 1 , 1 + 2 k - 1$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$

Como obtemos, por indução$0x \equiv 1 \pmod {2^0}$

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

onde o inverso é a soma de uma sequência geométrica. Eu mostrei a derivação para evitar o efeito coelho do chapéu: dada essa expressão, é fácil ver isso (dado que o valor entre parênteses é um número inteiro, que segue sua derivação como a soma de um número inteiro sequência) o produto à esquerda deve estar na classe de equivalência correta se for par.$x+1$

Isso fornece a função de 19 caracteres

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

que fornece respostas corretas para entradas que têm um inverso. No entanto, não é tão simples quando é par. Uma opção potencialmente interessante que encontrei é adicionar em vez de .$x$x&11

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

Isso parece dar valores sentinela de ou , mas ainda não provei isso.$0$$2^{n-1}$

Dando um passo adiante, podemos garantir um sentinela de para números pares alterando a expressão em :$0$$1 - (x+1)^n$$1 - 1^n$

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

Isso está relacionado à aplicação direta do teorema de Euler para o comprimento do código, mas terá um desempenho pior para grande . Se levarmos os argumentos ao contrário , podemos salvar um personagem e chegar a 22 caracteres :$n$n x f

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

Ruby - 88 caracteres

Use a função 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

Simplesmente a função recursiva da página wiki vinculada retorna 0 em erro.

Haskell, 42 bytes

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

Usando um algoritmo baseado no lema de Hensel que duplica o número de dígitos em cada iteração, isso é executado em menos de um segundo por n até cerca de 30 milhões !

Pitão , 9 bytes

.^Et^2Q^2

Experimente aqui!

Leva a entrada na ordem inversa. Ou, 9 bytes também: .^EtK^2QK.

Explicação

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

. ^ - Função Pow. O mesmo em Python (pow).
  E - A segunda entrada.
    ^ 2Q - E 2 ^ primeira entrada.
   t - Decrementado.
       ^ 2 - E 2 ^ primeira entrada novamente.

GAP, 39 bytes

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

f(x,n)retorna o inverso do xmódulo 2^ne dá uma mensagem de erro

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

se não existe inverso.