12219. Jasio kryptolog [AL_01_04]

Zadanie:
https://pl.spoj.com/problems/AL_01_04

Skrócony opis problemu:

Zadanie dotyczy szyfrowania RSA, więc na pewno przed jego rozwiązywaniem należy zapoznać się z tym systemem na przykład pod tym linkiem: RSA na wikipedii.

Na wejściu dostajemy dwie różne liczby pierwsze $p,q<4\cdot 10^9$ oraz liczbę $e<\phi(pq), \ \gcd(e,\phi(pq))=1$, tak że para $(pq,e)$ stanowi klucz publiczny szyfrowania. Oznaczmy $n=pq$. Chcemy się dowiedzieć ile komunikatów ze zbioru $\left\{0,..,n-1\right\}$ po zaszyfrowaniu taką metodą nie zmienia swojej postaci. Inaczej mówiąc pytamy o: $\left|\left\{M\in\left\{0,..,n-1\right\}: M^e \equiv M \pmod{n}\right\}\right|$ - liczbę punktów stałych szyfrowania RSA.

Rozwiązanie naiwne:

Sprawdzamy każdy komunikat $M$ ze zbioru $\left\{0,..,n-1\right\}$ i jeśli spełnia nasze warunki to zwiększamy wynik. Sprawdzenie odbywa się w czasie $O(\log n)$ (przyjmując, jak się często robi, że operacje mnożenia i dzielenia dwóch liczb odbywają się w czasie stałym - w rzeczywistości ta złożoność to $O(\log^3 n)$ w tym przypadku, o czym warto pamiętać), ponieważ musimy obliczyć $M^e \mod n$ klasycznym algorytmem szybkiego potęgowania modulo i sprawdzić czy otrzymaliśmy $M$.  Zatem złożoność obliczenia wyniku to $O(n\log n)$, co przy takich założeniach jak w zadaniu, nie pozwala zmieścić się w limitach czasowych.

Rozwiązanie wzorcowe:

Przyjrzyjmy się nieco dokładniej, kluczowej w zadaniu, kongruencji: $$M^e\equiv M \pmod{n}$$ Jest ona równoważna: $$pq | M(M^{e-1}-1) \Leftrightarrow \left(p|M \vee p|(M^{e-1}-1)\right) \wedge \left(q|M\vee q|(M^{e-1}-1)\right)$$ Ponieważ $p,q$ są liczbami pierwszymi. Bez straty ogólności obliczmy ile jest rozwiązań $p|M \vee p|(M^{e-1}-1)$ modulo $p$. Pierwszy przypadek mamy za darmo: $M\equiv 0 \pmod{p}$ i od tej pory przyjmijmy, że $M\not\equiv 0 \pmod{p}$.

Zostaje zatem sprawdzenie ile jest rozwiązań $M^{e-1}\equiv 1 \pmod{p}$, a równoważnie: $a^{e-1}\equiv 1 \pmod{p}$, gdzie $0\neq a=M\mod p$.

Przyszedł zatem czas na wytoczenie cięższej broni.

 
Lemat

Niech $p$ będzie liczbą pierwszą. Wówczas grupa multiplikatywna $\mathbb{Z}_p^*$ jest cykliczna tzn. posiada taki element $g\in \mathbb{Z}_p$, zwany generatorem, że $\left\{ g^n: 0 < n < p \right\} = \left\{1,...,p-1\right\}$.

Fakt ten jest bardzo znanym wynikiem z algebry i jego dowód, który pozwolę sobie pominąć, wymagałby rozpisywania się na tematy odchodzące od istoty zadania. Na pewno łatwo ten lemat zapamiętać (warto, mogę obiecać że jeszcze kiedyś jakieś moje zadanie będzie wymagało jego użycia ;-).

Na mocy powyższego lematu istnieje generator $g$ grupy $\mathbb{Z}_p^*$ oraz $g^x\equiv a \pmod{p}$ dla pewnego $x$. Zadanie zatem sprowadza się do znalezienia wszystkich takich $x \in \mathbb{Z}_{p-1}$, że: $$g^{x(e-1)}\equiv 1 \pmod{p}$$ Wiadomo jednak, że najmnieszą potęgą do której trzeba podnieść $g$, aby otrzymać $1 \mod p$, jest $p-1$. W takim razie powyższa kongruencja jest równoważna: $$(*) \ \ \ \ \ \ \ x(e-1) \equiv 0 \pmod{p-1}$$ Kładąc $d=\gcd(p-1,e-1)$ możemy kongruencję skrócić stronami: $$x\cdot \frac{e-1}{d} \equiv 0 \pmod{\frac{p-1}{d}}$$ I już prawie jesteśmy w domu. Liczby $\frac{e-1}{d}, \frac{p-1}{d}$ są względnie pierwsze, zatem istnieje odwrotność modularna $\frac{e-1}{d}$ modulo $\frac{p-1}{d}$ przez którą jak pomnożymy obustronnie powyższą kongruencję to dostaniemy: $$x\equiv 0 \pmod{\frac{p-1}{d}}$$ A takich $x$ spełniających $(*)$ jest dokładnie $d$ i są to: $0, \frac{p-1}{d}, 2\cdot\frac{p-1}{d},.., (d-1)\cdot\frac{p-1}{d}$.

Podsumowując znaleźliśmy w sumie $\gcd(p-1,e-1) + 1$ (wraz ze znalezionym na początku zerem) takich różnych liczb $a$, że: $M\equiv a \pmod{p}$ oraz: $$a \equiv 0 \vee a^{e-1} \equiv 1 \pmod{p}$$ Zupełnie analogicznie możemy znaleźć $\gcd(q-1,e-1) + 1$ takich różnych liczb $b$, że $M\equiv b \pmod{q}$ oraz: $$b \equiv 0 \vee b^{e-1} \equiv 1 \pmod{q}$$ Z kolei każdej takiej parze rozwiązań $a,b$ z Chińskiego twierdzenia o resztach odpowiada unikalne $X\in\left\{0,..,n-1\right\}$ takie, że $X^e\equiv X \pmod{n}$, czyli jest punktem stałym szyfrowania RSA o które pytamy. Stąd prosty wniosek, że punktów stałych jest: $$\left( \gcd(p-1,e-1)+1 \right)\cdot \left( \gcd(q-1,e-1)+1 \right)$$ Dzięki czemu jesteśmy w stanie każdy wynik policzyć w czasie $O(\log n)$ stosując algorytm Euklidesa.