Zapis wieżowy

Tym razem omówimy rozwiązanie zadania Zapis wieżowy z Akademickich Mistrzostw Polski w Programowaniu Zespołowym z 2006 roku.

Dla ciągu $|n$ liczb naturalnych $|a1,a2,...,an$ oraz liczby naturalnej $m$ należy wyznaczyć resztę z dzielenia przez $|m$ wieży potęgowej, w której liczby z ciągu są kolejnymi wykładnikami. Innymi słowy, mamy znaleźć wartość wyrażenia

an aa2 mod m. 1

Przykładowo, $| 23 3 mod 7 = 2,$ gdyż $| 23 8 3 = 3 = 6561 = 937 ⋅7+ 2.$ Oczywiście, bezpośrednie obliczanie potęg nie wchodzi w grę, gdyż ich wartości rosną coraz szybciej z każdym dodatkowym wykładnikiem i już liczba $3 432$ ma 3951 cyfr. Dla uproszczenia zapisu wieżę potęgową będziemy oznaczali przez $|a1 n.$

W rozwiązaniu zadania pomoże nam twierdzenie Eulera, które mówi, że dla względnie pierwszych liczb naturalnych $a$ i $|m$ spełniona jest kongruencja

φ m a 1 ≡ (mod m),

(*)

gdzie $φ(m)$ oznacza liczbę liczb względnie pierwszych z $m$ i nie większych niż ta liczba. Jeśli zatem liczby $a1$ i $m$ byłyby względnie pierwsze, to moglibyśmy:

wyznaczyć $φ(m),$
rekurencyjnie obliczyć rozwiązanie mniejszego problemu dla ciągu $|a2,...,an$ i modułu $|φ(m),$ czyli $|A2 = a2 n mod φ(m),$
korzystając z twierdzenia Eulera, wyznaczyć rozwiązanie

a = aa2 n = aγ⋅φ m = aγ⋅φ m ∗≡ aA2 (mod m). 1 n 1 1 1 1

Przypomnijmy, że jeśli znamy rozkład modułu na czynniki pierwsze $α |m = p α11⋯ pℓ`,$ to do obliczenia $φ (m)$ możemy wykorzystać następujący wzór:

p1-−1 p-ℓ−-1 φ(m) = m ⋅ p1 ⋯ pℓ .

(**)

Rozkład ten możemy znaleźć w czasie $√ -- |O( m ) ,$ przeglądając wszystkie potencjalne dzielniki liczby $|m$ nie większe niż $√ m-.$ Zatem w takim też czasie wykonamy krok 1 algorytmu. Z kolei potęgowanie $A2 a1 mod m$ z kroku 3 możemy wykonać w czasie $|O(log m),$ stosując metodę wielokrotnego podnoszenia do kwadratu. W sumie wykonamy $|n$ wywołań rekurencyjnych, w $i$ -tym wywołaniu obliczając $|A = a mod m , i i n i$ gdzie $m = m 1$ oraz $|mi = φ(mi −1)$ dla $|i⩾ 2,$ co da algorytm o złożoności czasowej $√ -- O (n m ).$

Zauważmy jednak, że ze wzoru $|(∗∗)$ widać, iż $|φ(x)$ dla nieparzystego $x$ jest liczbą parzystą, natomiast dla parzystego $|x$ mamy $|φ(x) ⩽ x2.$ Wynika z tego, że ciąg kolejnych modułów $|m1,m2,m3,...,1$ ma co najwyżej $|2log2m$ wyrazów, zatem wystarczy, że wykonamy $|min(n, 2log m) 2$ wywołań rekurencyjnych. A po drugie, pracę wykonaną we wszystkich wywołaniach kroku 1 można sumarycznie oszacować przez $√ -- |O( m ) .$ Zatem lepszym oszacowaniem czasu działania naszego algorytmu jest $-- O( √m + min(n, log m) log m),$ czyli po prostu $-- |O (√m ) .$

Niestety, abyśmy mieli pewność, że algorytm działa poprawnie, nie tylko liczby $a1$ i $m$ muszą być względnie pierwsze, ale również liczby $| ai$ i $| mi$ dla wszystkich $| i ⩾ 2.$ Na szczęście twierdzenie Eulera można uogólnić, aby działało również bez założenia o względnej pierwszości. Nowa wersja brzmi następująco: dla dowolnych liczb naturalnych $|a, m$ i $k$ spełniona jest kongruencja

as+k⋅φ mas≡ (mod m),

(***)

gdzie $s$ jest pewną liczbą zależną od $m,$ jednak nie większą niż $log m. 2$

Zanim udowodnimy to twierdzenie, zobaczmy, jak dzięki niemu naprawić nasz algorytm. Zmodyfikujemy go tak, aby nie tylko obliczał wartości $A , i$ ale również dodatkowy bit $ei$ równy 1 wtedy, gdy $ai n ⩾mi.$ Znowu pokażemy, jak wykonać krok (2) algorytmu: załóżmy zatem, że $|m ⩾2$ i obliczyliśmy już $|A2$ oraz $|e2.$

Wyznaczmy $|A1.$ Jeśli $|e2 = 0,$ to $a2 n < φ (m),$ więc $A2 = a2 n$ i wystarczy przyjąć $|A1 = aA12mod m.$ Z kolei jeśli $e2 = 1,$ to $|a2 n ⩾ A2 + φ(m) ⩾ log2m ⩾ s,$ czyli

a1 n = aa2 n = a γ−1 φ m ∗∗∗≡ aA2+ (mod m). 1 1 1

Zatem w obu przypadkach mamy $A2+e2 A1 = a1 mod m.$ Z kolei wyznaczyć $|e1$ można następująco: jeśli $a1 < 2,$ to $|e1 = 0,$ a w przeciwnym przypadku możemy wykonać potęgowanie $aA21+e2 ,$ w każdej iteracji domnażając jedno $a 1$ i sprawdzając, czy wynik osiągnął już $m$ (wykonamy co najwyżej $|log2m$ takich iteracji). Ostatecznie złożoność czasowa całego algorytmu nie zmienia się.

Pozostaje udowodnić dane wzorem $(∗ ∗∗)$ uogólnienie twierdzenia Eulera. Zdefiniujmy ciąg $di$ następująco:

d0 = nwd(a, m), di = nwd (a,---m---) dla i⩾ 1, d0⋯ di−1

oraz niech $|s$ będzie najmniejszą liczbą, taką że $ds = 1.$ Oznaczmy też $|D = d0⋯ ds−1.$

Liczba $m/D$ jest liczbą powstałą po usunięciu z $m$ wszystkich czynników pierwszych występujących w $a,$ zatem liczby $a$ i $m/D$ są względnie pierwsze. Z twierdzenia Eulera wynika zatem, że

k⋅φ m~D a ≡ 1 (mod m/D).

Ponadto każda z liczb $a/di$ jest całkowita, więc liczba $as/D$ również. Mnożąc powyższe równanie przez $as/D,$ dostajemy

as+k⋅φ m~D /D ≡ as/D (mod m/D).

Korzystając z faktu, że kongruencja $| x ≡ y (mod w)$ jest spełniona wtedy i tylko wtedy, gdy spełniona jest $|xD ≡ yD (mod wD),$ możemy przemnożyć przez $|D$ obie strony i moduł powyższego równania:

as+k⋅φ m~D ≡as (mod m).

Liczby $| D$ i $| m/D$ są względnie pierwsze, zatem z multiplikatywności funkcji $φ$ dostajemy $|φ(m) = φ(m/D) φ (D).$ Ponadto wykładniki w rozkładach na czynniki pierwsze liczb $|m/(d0⋯ di−1)$ zmniejszają się, więc $|s⩽ log m. 2$ Zatem ostatecznie dostajemy tezę twierdzenia:

as+k⋅φ mas≡ (mod m).