Znajdź x

Czas nadrobić zaległości i… porozmawiać o teorii liczb! Nie jest to co prawda działka, na której dobrze się znam, ale to nawet lepiej. W ramach rzeczonego odrabiania będzie o dwóch wydawałoby się różnych zadaniach, w których o dziwo przydaje się ta sama technika podnoszenia modulo kolejne potęgi liczby pierwszej. Zaczniemy od zadania Cryptoanalysis z pierwszej rundy zeszłorocznej edycji ukraińskich zawodów KPI Open, którego treść można znaleźć tutaj. Następnie spróbujemy rozwiązać (trochę ciekawsze) zadanie, które pojawiło się na zawodach ACM ICPC Asia Regional Kuala Lumpur 2010 (w których, niestety, nie było mi dane uczestniczyć), a jego treść można znaleźć tutaj. Przy czym tak naprawdę pomyślimy sobie o jego odrobinę utrudnionej wersji.

Celem zadania Cryptoanalysis jest udowodnienie, że protokół Diffiego-Hellmana nie bez przyczyny jest implementowany modulo liczba pierwsza. A dokładniej, mamy napisać program, który będzie łamał tenże protokół modulo 2^t, gdzie 0\leq t\leq 1024. Darujmy sobie streszczanie historyjki z treści i powiedzmy tylko, że mając dane g i A chcemy wyznaczyć takie x, że g^x = A\pmod{2^t}. Oczywiście g,A \in [0,2^t). Wystarcza to do rozwiązania całego zadania, o ile tylko umiemy szybko potęgować duże liczby. A przecież umiemy!

No dobrze. To może zacznijmy od jakiegoś prostego przypadku? Skoro liczymy modulo 2^t, naturalne jest osobne rozważenie sytacji, w której g jest parzyste (w szczególności, być może równe 0). Wtedy… wtedy życie jest łatwe. Jeśli bowiem g=2 g', nie ma sensu rozważać a>t! No bo przecież dla tak dużych a mamy g^a = g^{a-1}=0 \pmod{2^t}. No i fajnie, oznacza to bowiem, że możemy sobie w dość naiwny sposób sprawdzić wszystkich t+1 kandydatów na a. Od tego momentu będziemy więc zakładać, że g jest nieparzyste.

Może dałoby się jakoś ograniczyć zbiór sensownych kandydatów na a? Pewnie trochę by się dało. Twierdzenia Eulera (no, jedno z jego twierdzeń) mówi, że g^{\phi(2^t)}=1 \pmod{2^t}, gdzie \phi(2^t) mówi ile liczb 1,2,\ldots,2^t-1 jest względnie pierwszych z 2^t. Czyli g^{2^{t-1}}=1 \pmod{2^t}, a więc a\in [0,2^{t-1}). Co zmniejsza zbiór sensownych kandydatów do… skończonego, ale niestety wciąż dość dużego.

W tym momencie przyda nam się kilka prostych pojęć z teorii liczb. Rząd g modulo 2^t to po prostu najmniejsze k>0 dla którego g^k=1\pmod{2^t}. Jak widzieliśmy przed chwilą, takie k nie może przekroczyć 2^t, w niektórych sytuacjach może jednak być istotnie mniejsze. No, na przykład dla g=1 jest równe 1, a dla g=2^t-1 wynosi 2. Co ciekawe (i przydatne w dalszej części rozwiązania), rząd modulo 2^t zawsze jest potęgą 2. Można to łatwo wywnioskować mając pewną podstawową wiedzę na temat grup, ale można też policzyć na palcach. O ile ma się ich t.

Lemat. Rząd dowolnego nieparzystego g modulo 2^t (gdzie t>0) ma postać 2^i dla i\in [0,t).

Dowód. Spróbujmy zastosować indukcję względem t. Jeśli t=1, rząd dowolnego nieparzystego g to oczywiście 1=2^0. Jeśli t>1, to żeby g^k=1\pmod{2^t} musimy mieć także g^k=1\pmod{2^{t-1}}. Czyli.. rząd modulo 2^t musi być wielokrotnością rzędu modulo 2^{t-1} (to być może wymaga chwili zastanowienia). Powiedzmy, że rząd modulo 2^{t-1} miał postać 2^i dla jakiegoś i\in [0,t-1). Wtedy albo g^{2^i}=1\pmod 2^t, czyli rząd modulo 2^t jest dokładnie taki sam, albo g^{2^{i}}=1+2^{t-1}\pmod{2^t}. W tym drugim przypadku g^{2^{i+1}}=g^{2^i}g^{2^i}, czyli g^{2^{i+1}}=(1+2^{t-1})(1+2^{t-1})=1\pmod{2^t}, czyli rząd modulo 2^t to nic innego jak 2^{i+1}.

Powyższy dowód bardzo łatwo przerobić na efektywną procedurę, która wyznaczy rząd g modulo kolejne 2^1, 2^2, \ldots, 2^t. No i fajnie, ale przecież chodzi nam o coś innego: chcemy wyznaczyć x, dla którego g^x=A\pmod{2^t}, jak na razie umiemy odpowiedzieć na takie pytanie tylko dla A=1. A może nie tylko?

Spróbujmy uogólnić metodę z przedstawionego powyżej dowodu, czyli postarajmy się rozwiązać kolejne równania g^x=A\pmod {2^1}, g^x=A\pmod {2^2}, …, g^x=A\pmod {2^t}. Każde z tych równań może mieć wiele rozwiązań, ale tak naprawdę wystarczy nam tylko jedno: jeśli 2^{r_i} jest rzędem g modulo 2^i, równanie g^x=A\pmod {2^i} ma co najwyżej jedno rozwiązanie x\in [0,2^{r_i}). Co więcej, wszystkie inne rozwiązania to nic innego jak x+\alpha 2^{r_i}, czyli wyznaczenie tego unikalnego x\in [0,2^{r_i}) świetnie opisuje całą sytuację.

Na początku jest łatwo: na pewno g^0=A\pmod {2^1}, czyli dla i=1 mamy x=0. No, chyba że A jest parzyste, ale w takim przypadku możemy od razu zakończyć zabawę. Załóżmy więc, że znamy x\in [0,2^{r_i}) dla którego g^x=A\pmod{2^{i}} i chcemy wyznaczyć x'\in [0,2^{r_{i+1}}) dla którego g^{x'}=A\pmod{2^{i+1}}. Mamy dwa przypadki: jeśli r_{i+1}=r_i, jedyny sensowny kandydat na x' to x. Jeśli zaś r_{i+1}=r_i+1, robi się trochę ciekawiej. Mamy jednak tylko dwóch możliwych kandydatów na x', którymi są x i x+2^{r_i}. Wystarczy więc sprawdzić, który z nich spełnia g^{x'}=A\pmod {2^{i+1}}!

I to w zasadzie tyle. Oczywiście pozostaje jeszcze kwestia efektywnej implementacji opisanej wyżej metody, co (przede wszystkim) wymaga szybkiego operowania na dużych liczbach, a ponadto pewnej ostrożności podczas sprawdzania czy g^x=A\pmod {2^i}. Z tym drugim można sobie poradzić na przykład przechowując g^x\bmod {2^t} i g^{2^{r_i}}\bmod {2^t}, co pozwala na uniknięcie kosztownego potęgowania dla każdej z rozważanych wartości i.

Warto zauważyć, że kluczowe w całym rozwiązaniu było utrudnienie sobie życia. Zamiast rozwiązać jedno równanie modulo 2^t, rozwiązaliśmy ich o wiele więcej. Dzięki temu byliśmy jednak w stanie uzyskać kolejne rozwiązania przez podnoszenie poprzednich. Ta technika jest dość ogólna i może być wykorzystana także w innych zadaniach. Popatrzmy na jedno z nich, chyba odrobinę trudniejsze. Mimo niby zachęcającego tytułu.

W zadaniu Simple Encryption dla danego y\in [1,50000] chcemy wyznaczyć x \in [10^{11},10^{12}) dla którego y^x = x \pmod {10^{12}}. Ograniczenie y do 50000 wydaje się trochę sztuczne, tak naprawdę zajmiemy się więc ciekawszą wersją, w której y\in [1,10^{12}). Widać, że nie ma sensu rozważać większych wartość y, gdyż obliczenia i tak ostatecznie wykonujemy modulo 10^{12}.

W większości zadań, w których wykonujemy obliczenia modulo cośtam, warto zacząć od zastosowania chińskiego twierdzenia o resztach, dzięki któremu być może uda się zredukować problem do prostszej wersji, w której wykonujemy obliczenia modulo potęga liczby pierwszej. W tym konkretnym przypadku jest kłopotliwe z przynajmniej dwóch powodów: interesują nas tylko dostatecznie duże x, które co gorsza pojawia się w naszym równaniu także w wykładniku. Zacznijmy więc od uważnego przyjrzenia się wszystkim rozwiązaniom równania postaci y^x = x \pmod {10^k}.

Chcielibyśmy powiedzieć, że skoro obliczenia są wykonywane modulo 10^k, tak naprawdę interesuje nas tylko wartość x\pmod {10^k}. Nie jest to jednak prawda, a przynajmniej nie do końca: wartość y^x zależy od x\bmod \phi(10^k). Zakładamy tutaj, że y jest względnie pierwsze z 10^k, czyli niepodzielne przez 2 i 5, wtedy bowiem y^x = y^{x\bmod\phi(10^k)}\pmod {10^k}; wrócimy do tego założenia za jakiś czas. Czyli tak naprawdę interesuje nas tylko wartość x\bmod \mathrm{lcm}(10^k,\phi(10^k)). Lub, po prostym przekształceniu, x\bmod 2^{k+1}5^k.

Dość naturalnym pomysłem jest więc wygenerowanie wszystkich rozwiązań równania modulo 2*10^{12}, a następnie sprawdzenie, czy którekolwiek z nich należy do zakresu [10^{11},10^{12}). Nasuwają się jednak przynajmniej dwie wątpliwości:

  1. czy tych wszystkich rozwiązań nie może być przypadkiem bardzo dużo?
  2. a nawet jeśli jest ich niewiele, czy umiemy je wszystkie szybko wygenerować?

Na razie nie przejmujmy się tą pierwszą kwestią i skupmy się na w miarę efektywnym wygenerowaniu wszystkich rozwiązań. Być może okaże się to ślepą uliczką, ale nie uprzedzajmy faktów.

Chcielibyśmy wygenerować wszystkie x\in [0,2*10^k) dla których y^x=x\pmod {10^k}. Jeśli k=0, nie wydaje się to trudne. Skoro tak, to może dałoby się tutaj zastosować indukcję? Innymi słowy, może mając wszystkie x\in [0,2*10^k), dla których y^x=x\pmod {10^k}, dałoby się (szybko) wygenerować x'\in [0,2*10^{k+1}), dla których y^{x'}=x'\pmod {10^{k+1}}? Jest to o tyle kuszące, że każde x' w naturalny sposób odpowiada dokładnie jednemu x = x'\pmod {2*10^k}. Spróbujmy więc pójść w drugą stronę, czyli dla każdego x wygenerujmy wszystkie odpowiadające mu x'! Skoro x' = x + \alpha 2*10^k, możemy po prostu przejrzeć wszystkie możliwe \alpha=0,1,\ldots,9 i sprawdzić, czy faktycznie y^{x'} = x'\pmod {10^{k+1}}, co wymaga wykonania jednego potęgowania i kilku operacji arytmetycznych na liczbach modulo 10^{k+1}. A więc wydaje się być dość efektywne. Rzeczywiście, jeśli oznaczymy przez L_k zbiór wszystkich rozwiązań x dla danego k, przy odrobinie wysiłku nasz całkowity czas działania to \mathcal{O}(\sum_k |L_k|). No dobrze, ale czy to wystarczy?

Na to pytanie najprościej odpowiedzieć wykonując eksperyment, czyli po prostu zaimplementować naszkicowane wyżej rozwiązanie. Okazuje się, że działa ono całkiem szybko, i ze sporym zapasem mieści się w limicie czasu. W tym momencie w zasadzie można by uznać zadanie za rozwiązane, i z czystym sumieniem zająć się czymś ciekawszym. Ale może warto choć przez chwilę zastanowić się dlaczego to co napisaliśmy szybko działa? No, a na pewno warto zastanowić się nad przypadkiem x podzielnego przez 2 lub 5. Ta druga kwestia okazuje się jednak o tyle nieinteresująca, że nasze rozwiązanie w zasadzie działa również dla takich x, skupmy się więc na oszacowaniu jego czasu działania.

Lemat. Jeśli 2,5 \nmid y i k>0, mamy |L_{k+1}| \leq 2 |L_k|.

Weźmy x dla którego y^x=x \pmod {10^k}. Pokażemy, że co najwyżej dwie wartości \alpha pozwalają nam na uzyskanie poprawnego x' = x + \alpha 2*10^k. Załóżmy, że istnieją \alpha < \alpha', dla których:

\begin{array}{rcl} y^{x + \alpha 2*10^k} &=& x + \alpha 2*10^k \pmod {10^{k+1}}\\ y^{x + \alpha' 2*10^k} &=& x + \alpha' 2*10^k \pmod {10^{k+1}} \end{array}

Stąd otrzymujemy, że:

y^{x} \left[(y^{2*10^k})^\alpha - (y^{2*10^k})^{\alpha'} \right] = 2*10^k (\alpha - \alpha') \pmod {10^{k+1}}

Czyli tak naprawdę:

\begin{array}{rcl} y^{x} \left[(y^{2*10^k})^\alpha - (y^{2*10^k})^{\alpha'} \right] &=& 0 \pmod {2^{k+1}}\\ \\ y^{x} \left[(y^{2*10^k})^\alpha - (y^{2*10^k})^{\alpha'} \right] &=& 2*10^k (\alpha - \alpha') \pmod {5^{k+1}} \end{array}

Popatrzmy na (y^{2*10^k})^\alpha - (y^{2*10^k})^{\alpha'}. Łatwo zauważyć, że obydwa składniki zerują się modulo 2^{k+1}, czyli pierwszy warunek jest zawsze spełniony. Podobnie, obydwa składniki zerują się modulo 5^{k+1} jeśli k>0, czyli drugi warunek to wtedy tak naprawdę 5^{k+1} | 2*10^k (\alpha - \alpha'), a więc \alpha' = \alpha + 5.

Wiemy, że y^x = x \pmod {5^{k}}, czyli y^x = x + \beta 5^k \pmod {5^{k+1}}. To pozwala nam przekształcić y^{x+\alpha 2*10^k} = x+\alpha 2*10^k \pmod {5^{k+1}} do prostej postaci \beta = \alpha 2^{k+1} \pmod 5, czyli wartość \alpha jest jednoznacznie wyznaczona!

Z powyższego lematu od razu dostajemy, że |L_k| =\mathcal{O}(2^k). Eksperymenty wydają się wskazywać, że tak naprawdę |L_k|=2, ale niestety nie mam pomysłu na pokazanie tego bez zagrzebywania się w dość męczących rachunkach. Może taki pomysł ma jednak ktoś z Was?

Na koniec jeszcze jedna dygresja. Sztuczka z konstruowaniem rozwiązań modulo coraz większe potęgi nieco przypomina lemat Hensela (Hensla?), o który warto zapytać swojego ulubionego znajomego matematyka.

Advertisements

4 myśli nt. „Znajdź x

  1. Lemat Hensela pozwala na podobne sztuczki w sytuacji gdy rozważamy równanie wielomianowe postaci q(x)=0 \pmod{p^k}. Metoda jest taka, że startujemy od rozwiązania q(x)=0 \pmod{p} a następnie wykonujemy „podnoszenie” do rozwiązania modulo p^2,p^3,...,p^k,p^{k+1},.... Uzyskane w ten sposób rozwiązania, zbiegają w naturalny sposób do rozwiązania tego równania w zbiorze liczb p-adycznych (czyli w pewnym sensie modulo p^\infty). Ta teoria działa bardzo dobrze dla wielomianów, ponieważ są to obiekty czysto algebraiczne. Natomiast w tych zadaniach jest trudniej, bo mamy do czynienia z równaniem wykładniczym względem x. Dlaczego mimo wszystko ta technika działa? Według mnie, dlatego, że szczęśliwie \phi(2^k)=2^{k-1} oraz \phi(10^k) też bardzo przypomina potęgę dziesiątki. Ogólnie niestety nie zawsze \phi(n) wygląda jak n (dokładniej: ma nowe czynniki pierwsze w stosunku do n).

    • Aha, zapomniałem wspomnieć, że równanie wielomianowe modulo liczba pierwsza p „jakoś” da się rozwiązać 😉

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s