Biorąc pod uwagę dwie liczby dodatnie xi za npomocą x<2^n, napisz najkrótszą możliwą funkcję do obliczenia x^-1 mod 2^n. Innymi słowy, znajdź ytaki, że x*y=1 mod 2^n.

Twoja funkcja musi zostać ukończona przynajmniej w rozsądnym czasie n=64, aby wyczerpujące wyszukiwanie nie zadziałało.

Jeśli odwrotność nie istnieje, musisz jakoś to wskazać dzwoniącemu (wyrzuć wyjątek, zwróć wartość wartownika itp.).

Jeśli zastanawiasz się, od czego zacząć, wypróbuj rozszerzony algorytm euklidesowy .

Python 95 89

cjest twoją funkcją. Zwraca 0, jeśli nie ma odwrotności (tj. Gdy x jest parzyste).

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 bajtów

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

Zwraca 0 dla parzystego x . Wykorzystuje twierdzenie Eulera, z obserwacją, że 2 ^ n - 1 można podzielić przez 2 ^ ( n - 1) - 1, za pomocą wbudowanego szybkiego modularnego potęgowania Pythona. Jest mnóstwo wystarczająco szybki dla n do 7000 lub tak, gdzie zaczyna robić więcej niż około sekundy.

Mathematica - 22

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

f[x,n]zwraca yz x*y=1 mod 2^n, w przeciwnym raziex is not invertible modulo 2^n

GolfScript (23 znaki)

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

Wynik wartownika dla nieistniejącej odwrotności to 0 .

Jest to proste zastosowanie twierdzenia Eulera . , więc 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}$

Niestety jest to zbyt duża wykładnicza wartość, aby obliczyć bezpośrednio, więc musimy użyć pętli i dokonać modularnej redukcji w pętli. Krok iteracyjny to i mamy do wyboru wariant podstawowy: albo z$x^{2^k-1} = \left(x^{2^{k-1}-1}\right)^2 \times x$k=1

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

lub k=2z

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

Pracuję nad innym podejściem, ale wartownik jest trudniejszy.

Kluczową obserwacją jest to, że możemy budować odwrotność w górę krok po kroku: jeśli a następnie x y ∈ { 1 , 1 + 2 k - 1$xy \equiv 1 \pmod{2^{k-1}}$ , a jeśli x jest nieparzyste, mamy x ( y + x y - 1 ) ≡ $xy \in \{ 1, 1 + 2^{k-1} \} \pmod{2^k}$$x$ . (Jeśli nie jesteś przekonany, sprawdź oba przypadki osobno). Możemy więc zacząć od dowolnego odpowiedniego przypadku podstawowego i zastosować transformację y ′ = ( x + 1 ) y - $x(y + xy-1) \equiv 1 \pmod{2^k}$$y' = (x+1)y - 1$ odpowiednią liczbę razy.

Ponieważ otrzymujemy przez indukcję$0x \equiv 1 \pmod {2^0}$

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

gdzie odwrotność jest sumą sekwencji geometrycznej. Pokazałem wyprowadzenie, aby uniknąć efektu królika poza kapeluszem: biorąc pod uwagę to wyrażenie, łatwo to zauważyć (biorąc pod uwagę, że wartość w nawiasach kwadratowych jest liczbą całkowitą, która wynika z jego wyprowadzenia jako sumy liczby całkowitej sekwencja) produkt po lewej musi być w odpowiedniej klasie równoważności, jeśli jest parzyste.$x+1$

To daje funkcję 19-znakową

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

która daje poprawne odpowiedzi dla danych wejściowych, które mają odwrotność. Jednak nie jest to takie proste, gdy jest parzyste. Jedną potencjalnie interesującą opcją, którą znalazłem, jest dodanie zamiast .$x$x&11

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

$0$$2^{n-1}$ , ale jeszcze tego nie udowodniłem.

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

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

$n$n x f

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

Ruby - 88 znaków

Użyj funkcji 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

Po prostu funkcja rekurencyjna z połączonej strony wiki zwraca 0 w przypadku błędu.

Haskell, 42 bajty

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

Wykorzystując algorytm oparty na lemacie Hensela, który podwaja liczbę cyfr w każdej iteracji, biegnie to w mniej niż sekundę dla n do około 30 milionów !

Pyth , 9 bajtów

.^Et^2Q^2

Wypróbuj tutaj!

Pobiera dane wejściowe w odwrotnej kolejności. Lub 9 bajtów za: .^EtK^2QK.

Wyjaśnienie

. ^ Et ^ 2Q ^ 2 - Pełny program.

. ^ - Funkcja Pow. To samo w Pythonie (pow).
  E - Drugie wejście.
    ^ 2Q - I 2 ^ pierwsze wejście.
   t - Zmniejszony.
       ^ 2 - I 2 ^ ponownie pierwsze wejście.

GAP, 39 bajtów

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

f(x,n)zwraca odwrotność xmodulo 2^ni wyświetla komunikat o błędzie

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

jeśli nie istnieje odwrotność.