Zadanie jest następujące: Biorąc pod uwagę dodatnią liczbę całkowitą xi liczbę pierwszą n > x, wypisz najmniejszą dodatnią liczbę całkowitą ytaką, że (y * y) mod n = x. Ważną częścią tego pytania jest określony poniżej termin, który wyklucza rozwiązania dotyczące brutalnej siły.

Jeśli nie ma takiej wartości, ykod powinien zostać wypisany N.

Przypadki testowe

(2, 5, N), 
(3, 5, N), 
(4, 5, 2),
(524291, 1048583, N),
(529533, 1048583, N),
(534775, 1048583, 436853),
(540017, 1048583, 73675),
(536870913, 1073741827, 375394238),
(542239622, 1073741827, 267746399),
(547608331, 1073741827, N),
(552977040, 1073741827, 104595351),
(1099511627676, 1099511627791, N),
(1099511627677, 1099511627791, 269691261521),
(1099511627678, 1099511627791, 413834069585),
(1267650600228229401496703204376, 1267650600228229401496703205653, 5312823546347991512233563776),
(1267650600228229401496703204476, 1267650600228229401496703205653, N)
(1267650600228229401496703204576, 1267650600228229401496703205653, N)
(1267650600228229401496703204676, 1267650600228229401496703205653, 79905476259539917812907012931)

Wejście i wyjście

Możesz przyjmować dane wejściowe i przekazywać dane w dowolny dogodny sposób. Jeśli nie lubisz generować danych, zrobi Nto dowolna Falseywartość.

Ograniczenia

Twój kod musi odpowiadać na wszystkie przypadki testowe w czasie krótszym niż 1 minuta na standardowym pulpicie. Ten limit czasowy ma jedynie na celu zapobieganie odpowiedziom z użyciem siły brutalnej i oczekuję, że dobre odpowiedzi będą działać niemal natychmiast. Nie możesz używać żadnej biblioteki lub wbudowanego rozwiązania, które rozwiązałoby ten problem lub które sprawdza, czy liczba jest kwadratową resztą.

Pyth, 83 82 bajtów

=eAQM.^GHQKf%=/H=2;1=gftgT/Q;1HJg~gGHh/H2WtG=*J=gT^2t-K=Kfq1gG^2T1=%*G=^T2Q;hS%_BJ

Zestaw testowy

Ten program implementuje algorytm Tonelli-Shanksa . Napisałem to, uważnie śledząc stronę Wikipedii. Przyjmuje jako dane wejściowe (n, p).

Brak pierwiastka kwadratowego jest zgłaszany przez następujący błąd:

TypeError: pow() 3rd argument not allowed unless all arguments are integers

Jest to bardzo misternie golfowy kod, napisany w stylu imperatywnym, w przeciwieństwie do bardziej popularnego stylu funkcjonalnego Pytha.

Jedynym subtelnym aspektem Pytha, którego używam jest to =, że jeśli nie następuje bezpośrednio po nim zmienna, szuka w programie następnej zmiennej do przodu, następnie przypisuje wynik następującego wyrażenia do tej zmiennej, a następnie zwraca ten wynik. W całym objaśnieniu będę odwoływał się do strony wikipedii: algorytm Tonelli-Shanksa , ponieważ jest to algorytm, który wdrażam.

Wyjaśnienie:

=eAQ

Atrwa 2-krotnego jako wejście i przydziela wartości Gi Hodpowiednio, i zwraca jego wejście. Qjest początkowym wejściem. ezwraca ostatni element sekwencji. Po tym fragmencie, Gto ni Hi Qsą p.

M.^GHQ

Mdefiniuje funkcję 2 wejść g, gdzie wejściami są Gi H. .^jest szybką modułową funkcją potęgowania Pytha. Ten fragment kodu goznacza mod potęgowania Q.

Kf%=/H=2;1

fdefiniuje powtarzanie aż do fałszywej pętli i zwraca liczbę iteracji, dla których działa, podane 1jako dane wejściowe. Podczas każdej iteracji pętli dzielimy Hprzez 2, ustawiamy Hna tę wartość i sprawdzamy, czy wynik jest nieparzysty. Kiedy to nastąpi, przestajemy. Kprzechowuje liczbę wykonanych iteracji.

Jedną z bardzo trudnych rzeczy jest =2;nieco. =wyszukiwania do przodu do następnej zmiennej, która jest T, tak Tjest ustawiony na 2. Jednakże Twewnątrz fpętli licznik iteracji, więc używamy ;, aby uzyskać wartość Tz globalnym środowisku. Ma to na celu zaoszczędzenie kilku bajtów białych znaków, które w innym przypadku byłyby potrzebne do oddzielenia liczb.

Po tym fragmencie Kpochodzi Sz artykułu w Wikipedii (wiki) i Hpochodzi Qz wiki i Tjest 2.

=gftgT/Q;1H

Teraz musimy znaleźć kwadratowy mod bez pozostałości p. Wymusimy to brutalnie, stosując kryterium Eulera. /Q2to (p-1)/2, ponieważ /jest podłogą podziału, tak ftgT/Q;1znajdzie Pierwsza liczba Tw którym T ^ ((p-1)/2) != 1, zgodnie z życzeniem. Przypomnij sobie, że ;ponownie ściąga Tz globalnego środowiska, które wciąż ma 2. Ten wynik pochodzi zz wiki.

Następnie, aby utworzyć cz wiki, potrzebujemy z^Q, więc zawijamy powyższe g ... Hi przypisujemy wynik T. Teraz Tjest cz wiki.

Jg~gGHh/H2

Załóżmy oddzielić to: ~gGH. ~jest podobny =, ale zwraca oryginalną wartość zmiennej, a nie jej nową wartość. Zwraca więc, że Gpochodzi nz wiki.

To przypisuje Jwartość n^((Q+1)/2), która pochodzi Rz wiki.

Teraz obowiązują następujące zasady:

~gGH

To przypisuje Gwartość n^Q, która pochodzi tz wiki.

Teraz mamy ustawione zmienne pętli. M, c, t, Rz wiki są K, T, G, J.

Ciało pętli jest skomplikowane, więc przedstawię go z białą spacją, tak jak to napisałem:

WtG
  =*J
    =
      gT^2
        t-
          K
          =Kfq1gG^2T1
  =%*G=^T2Q;

Najpierw sprawdzamy, czy Gjest 1. Jeśli tak, wychodzimy z pętli.

Kolejny działający kod to:

=Kfq1gG^2T1

Tutaj szukamy pierwszej itakiej wartości G^(2^i) mod Q = 1, zaczynając od 1. Wynik zostaje zapisany w K.

=gT^2t-K=Kfq1gG^2T1

Tutaj bierzemy starą wartość K, odejmujemy nową wartość K, odejmujemy 1, podnosimy 2 do tej mocy, a następnie podnosimy Tdo tej modów mocy Q, a następnie przypisujemy wynik do T. To Trówna się bz wiki.

Jest to również linia, która kończy pętlę i kończy się niepowodzeniem, jeśli nie ma rozwiązania, ponieważ w takim przypadku nowa wartość Kbędzie równa starej wartości K, 2 zostanie podniesiona do -1, a modułowe potęgowanie spowoduje błąd.

=*J

Następnie mnożymy Jprzez powyższy wynik i przechowujemy go z powrotem J, Raktualizując go.

=^T2

Następnie poprawiamy Ti zapisujemy wynik z powrotem T, ustawiając z Tpowrotem cna wiki.

=%*G=^T2Q

Następnie mnożymy Gprzez ten wynik, bierzemy mod Qi zapisujemy wynik z powrotem G.

;

I kończymy pętlę.

Po zakończeniu pętli Jpierwiastek kwadratowy z nmod p. Aby znaleźć najmniejszy, używamy następującego kodu:

hS%_BJ

_BJtworzy listę Ji jej negację, %domyślnie przyjmuje Qza swój drugi argument i używa domyślnego zachowania Pytha do zastosowania % ... Qdo każdego elementu sekwencji. Następnie Ssortuje listę i hbierze pierwszego członka, minimum.

Python 2, 166 bajtów

def Q(x,n,a=0):
 e=n/2
 while pow(a*a-x,e,n)<2:a+=1
 w=a*a-x;b=r=a;c=s=1
 while e:
    if e%2:r,s=(r*b+s*c*w)%n,r*c+s*b
    b,c=(b*b+c*c*w)%n,2*b*c;e/=2
 return min(r,-r%n)

SageMath , 93 bajty

Przez redukcję do znacznie trudniejszego problemu, dla którego SageMath ma wystarczająco szybkie wbudowane funkcje.

def f(x,n):g=primitive_root(n);k=Zmod(n)(x).log(g);y=pow(g,k//2,n);return k%2<1and min(y,n-y)

Wypróbuj na SageMathCell

Haskell , 326 bajtów

Zwykle lubię odpowiedzi na brutalną siłę. Ponieważ termin zdecydowanie mnie odradza, oto najbardziej skuteczny sposób, jaki znam:

r p=((\r->min(mod(-r)p)r)$).f p
f p x|p==2=x|q x=f 0 0|mod p 4==3=x&div(p+1)4|let(r,s)=foldl i(p-1,0)[1..t 1o]=m$x&(d$r+1)*(b&d s)where q a=1/=a&o;m=(`mod`p);a&0=1;a&e|even e=m$a&d e^2|0<1=m$(a&(e-1))*a;b=[n|n<-[2..],q n]!!0;i(a,b)_|m(x&d a*b&d b)==p-1=(d a,d b+o)|0<1=(d a,d b);o=d p;t y x|even x=t(y+1)(d x)|0<1=y;d=(`div`2)

Wypróbuj online!

Jestem pewien, że można to jeszcze pograć w golfa, ale na razie powinno to wystarczyć.