%\author{Савон Юлия}
%\date{22 марта 2016}
\Section{Окончание лекции по теории чисел}{1 июня}{Савон Юлия}
\Subsection{3 задачи про разные степени}

\textbf{1)}(Напоминалка)Первообразный корень $g^{p - 1} = 1$ vs $g^{\frac{p - 1}{x}} = 1 (x > 1)$, второе человечество умеет решать за $fact(x) + \log^2{n}$, факторизацию умеем за $\sqrt[4]{x} \cdot gcd(x)$

\textbf{2)}$x^a \equiv b (mod$ $p)$ - Дискретное логарифмирование  

\textbf{3)}(решается через 1 и 2) $x^a \equiv b (mod p)$ - извлечение корня, где p - простое

\Subsection{Решения:} 

\textbf{2) Baby-Step-Giant-Step}

Ассимптотика: $\mathcal{O}(\sqrt{p})$

Примем $k = \lceil\sqrt{p}\rceil$

Вспомним старую добрую Теорему Ферма $a^{p - 1} \equiv 1 (mod p) \Rightarrow 0 \leq x < p$ <- т.к. остатки циклятся

Пусть мн-во $A = \{a^0, a^-1, a^-2, ..., a^{-(k - 1)}\}$ Считаем за $\mathcal{O}(\log{p} + k)$, сначала ищем $a^{-(k - 1)}$, а потом за линию оставшиеся отрицательные степени.

$B = \{a^0, a^k, a^2k, ..., a^{k(k - 1)}\}$ <- большие степени 

Из большой и маленькой степени можно скомпоновать любую от 0 до p(т.к. поделив любую степень на k, получим остаток и частное, не превосходящие k). 

Этим и воспользуемся. Положив все большие в Хеш-таблицу(Map), где ключом будет значение, а значением, спепень, в которую возвели.

\lstinputlisting{savon/find_grade.cpp} 

Тем самым мы решили задачу за $\mathcal{O}(\sqrt{n})$

\textbf{3) Сведение к первым 2-м.} 

Ассимптотика: $\mathcal{O}(\sqrt{p})$

$x^a \equiv b(mod p)$, впомним, что существует натуральный логарифм.

Заменим переменные $x = g^i$, $b=g^j$ (эту задачу мы уже научились решать в пункте 2) )

$g^{i \cdot a} \equiv g^j$ (mod p), теперь задача поменялась и нужно найти i. Теоритически умеем делать это $\mathcal{O}(\log{p})$

$i \cdot a \equiv j \cdot (p - 1) \Rightarrow i = j \cdot a^-1$

\textbf{Замечание:} Ни факторизацию, ни дискретное логарифмирование человечество за $\mathcal{O}(\log_2^k{n})$ решать не умеет.

Ассимптотика решения Факторизации: 

1)$\frac{\sqrt{n}}{\log{n}}$

2)$\sqrt[4]{n}^{\frac{1}{4}} \cdot gcd$  - реализацию первых двух алгоритмов знаем

3)$exp(\sqrt{\log{n}})$ - алг. Крайчика

4)$exp(\sqrt[3]{\log{n}})$ - Элептические кривые, алг. Ленстры

\textit{Напоминалка:} $exp(k \cdot \log \cdot \log) = \log^k$ $exp(k\cdot \log) = n^k$

 
