Diberi dua angka positif xdan ndengan x<2^n, tulis fungsi sesingkat mungkin untuk dihitung x^-1 mod 2^n. Dengan kata lain, temukan yitu x*y=1 mod 2^n.

Fungsi Anda harus menyelesaikan setidaknya dalam waktu yang wajar n=64, sehingga pencarian lengkap tidak akan berfungsi.

Jika kebalikannya tidak ada, Anda harus menunjukkan itu kepada penelepon entah bagaimana (melemparkan pengecualian, mengembalikan nilai sentinel, dll).

Jika Anda bertanya-tanya harus mulai dari mana, coba Algoritma Euclidean Diperpanjang .

Python 95 89

cadalah fungsi anda. Mengembalikan 0 jika tidak ada terbalik (yaitu ketika x genap).

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 byte

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

Ini mengembalikan 0 bahkan x . Ia menggunakan teorema Euler, dengan pengamatan bahwa 2 ^ n - 1 dapat habis dibagi 2 ^ ( n - 1) - 1, melalui eksponensial modular cepat built-in Python. Ini cukup cepat untuk n hingga 7000 atau lebih, di mana ia mulai mengambil lebih dari sekitar satu detik.

Mathematica - 22

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

f[x,n]kembali ydengan x*y=1 mod 2^n, jika tidakx is not invertible modulo 2^n

GolfScript (23 karakter)

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

Hasil sentinel untuk invers yang tidak ada adalah 0.

Ini adalah aplikasi sederhana dari teorema Euler . , jadi 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}$

Sayangnya itu eksponensial terlalu besar untuk dihitung secara langsung, jadi kita harus menggunakan loop dan melakukan reduksi modular di dalam loop. Langkah berulang adalah dan kami memiliki pilihan kasus dasar: baik dengan$x^{2^k-1} = \left(x^{2^{k-1}-1}\right)^2 \times x$k=1

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

atau k=2dengan

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

Saya sedang mengerjakan pendekatan lain, tetapi penjaga itu lebih sulit.

Pengamatan kuncinya adalah kita dapat membangun invers up sedikit demi sedikit: jika $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$ genap.

Itu memberi fungsi 19-char

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

$x$x&11

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

$0$$2^{n-1}$ , tapi saya belum membuktikannya.

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

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

$n$n x f

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

Ruby - 88 karakter

Gunakan fungsinya 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

Cukup fungsi rekursif dari halaman wiki yang tertaut, mengembalikan 0 pada kesalahan.

Haskell, 42 byte

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

Menggunakan algoritma berdasarkan lemens Hensel yang menggandakan jumlah digit di setiap iterasi, ini berjalan di bawah satu detik untuk n hingga sekitar 30 juta !

Pyth , 9 byte

.^Et^2Q^2

Coba di sini!

Mengambil input dalam urutan terbalik. Atau, 9 byte juga: .^EtK^2QK.

Penjelasan

. ^ Et ^ 2Q ^ 2 - Program lengkap.

. ^ - Fungsi Pow. Hal yang sama dengan Python (pow).
  E - Input kedua.
    ^ 2Q - Dan 2 ^ input pertama.
   t - Dikurangi.
       ^ 2 - Dan 2 ^ input pertama lagi.

GAP, 39 byte

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

f(x,n)mengembalikan kebalikan dari xmodulo 2^ndan memberikan pesan kesalahan

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

jika tidak ada terbalik.