\Section{Теория чисел}{23 мая}{Черепанов Валерий}

\begin{Def}{$\Z/p\Z = \mathbb{F}_p$}
  поле остатков по модулю p.
\end{Def}

\begin{Def}{$(\Z/m\Z)^*$}
  Группа по умножению $\{a\colon (a, m)=1 \cap 1 \leq a < m\}$.
\end{Def}

\begin{Def}{Линейное диофантово уравнение}
  ($a, b, c$ даны, нужно найти $x, y$).
  $$ax+by+c=0; x, y \in \Z$$
\end{Def}

\THEE{Деление}
$\frac a b = a\cdot b^{-1}$

\Subsection{Расширенный алгоритм Евклида}

Чтобы решить само уравнение, нужно домножить результат алгоритма на $c/\text{gcd}(a, b)$. Если без остатка не делится, то решения нет.

\begin{code}
int Euclid (int a, int b, int &x, int &y) { // ax + by = gcd(a, b)
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  int y = Euclid(b, a%b, y, x); // b*y+(a-(a/b)b)x=gcd
  y -= x*(a/b);
  return y;
}
\end{code}
    
\begin{Lm}{(Без доказательства)}
  Все промежуточные и конечные $x$ и $y$ по модулю не больше $\max(|a|, |b|)$.
\end{Lm}

\Subsection{Обратные в кольце по модулю}

$a$ и $m$ даны, хотим найти $x$.
\begin{gather*}
  a\cdot x = 1 \mod m \\
  ax + my = 1 = \text{gcd}(a, m)
\end{gather*}

Другой способ:
\begin{gather*}
  a^{p-1}=1\mod p \Rightarrow x = a^{p-2} \\
  a^{\phi(m)} = 1 \mod m \Rightarrow x = a^{\phi(m)-1}
\end{gather*}

\textit{Замечание}
Функцию Эйлера считать долго!
$$\phi(n) = n \prod \frac{p_i-1}{p_i};~n = \prod p_i^{\alpha_i}$$

\Subsection{Возведение в степень за $\O(\log n)$}

\begin{code}
int pow(int x, int y) {
  res = pow(x, n / 2);
  res *= res;
  return (n & 1) ? res * x : res;
}
\end{code}


\Subsection{Обратные для чисел от $1$ до $k-1$ по модулю за $\O(k)$}

Модуль $m$, считаем динамикой.
\begin{Thm}
  $$i^{-1} = -\lfloor\frac m i\rfloor \cdot (p~\text{mod}~i)^{-1}$$
\end{Thm}

\begin{proof}
\begin{gather*}
  m~\text{mod}~i = m - \lfloor \frac m i \rfloor \cdot i \\
  m~\text{mod}~i = - \lfloor \frac m i \rfloor \cdot i \mod m \\
  1 = - \lfloor \frac m i \rfloor \cdot i \cdot (m~\text{mod}~i)^{-1} \\
  i^{-1} = -\lfloor \frac m i \rfloor \cdot (m~\text{mod}~i)^{-1}
\end{gather*}
\end{proof}

\Subsection{RSA}

Два типа шифрования:
\begin{description}
  \item[Симметричная криптография] Ключ позволяет зашифровать и расшифровать сообщение. Пример: xor.
  \item[Криптография с открытым ключем] Боб хочет послать сообщение Алисе и шифрует его открытым ключем Алисы $(e)$, который виден всем. Для расшифровки Алисе понадобится ее закрытый ключ $(d)$, который знает только она. Функции для шифровки и расшифровки открыты.
\end{description}

RSA вкратце:
\begin{gather*}
  n = pq;~p, q \in \mathbb{P} \\
  \phi(n) = (p-1)(q-1) \\
  e\cdot d = 1 \mod \phi(n) \\
  e, d < \phi(n) \\
\end{gather*}
Выберем случайные $p$, $q$ и $e$, а $n$, $\phi(n)$ и $d$ вычислим по формулам.
Тогда открытым ключем будет $<e, n>$, а закрытым "--- $<d, n>$.

Зашифруем и расшифруем:
$$m \Rightarrow m^e (n) \Rightarrow (m^e)^d (n) = m^{\phi(n)\cdot k + 1}(n) = m(n)$$

Алгоритм надежен настолько, насколько сложна задача факторизации чисел. Числа умеют факторизовать так:
\begin{MyList}
  \item $\O(n)$ Тривиально.
  \item $n^{1/4}\cdot gcd$ Эвиристика Полларда, будет в курсе.
  \item $e^{^3\sqrt{\ln n}}$
\end{MyList}

Обычно в RSA используют ключ длины $2048$. Можно шифровать за $\Theta(k^3/w^2)$ --- $k$ операций ``деление по модулю''.
Можно деление реализовать за $\O(k \log k)$, получается $\O(k^3)$.

%{1+\log_2 3}$ (умножение Карацубы).

\Subsection{Первообразный корень}
\begin{Def}{$F_p\colon 1, g, g^2, g^3, \ldots, g^{p-2}$}

  Такой корень, который пораждает всю мультипликативную группу.
\end{Def}

Из алгебры знаем, что он существует.

Алгоритм для поиска:
\begin{code}
return random[1, p-1]
\end{code}

\begin{Lm}
  $Pr \geq \frac 1 {\ln \ln p}$
\end{Lm}
\begin{proof}
  Алгоритм ``ткнет'' в $g^i$, нам лишь нужно, чтобы $\text{gcd}(i, p-1)=1$.
  $$\frac{\phi(p-1)}{p-1} \leq \frac 1 {\ln \ln p}$$
  Покажим, что $\phi$ не бывает слишком маленьким. Оценим худший вариант: произведение простых чисел. $1/2\cdot2/3\cdot4/5\cdot6/7\cdot \dots$. Оценивается так: заменим произведение на сумму логарифмов и возьмем два первых члена ряда Тейлора.
\end{proof}

Проверка корректности (следующие условия должны выполняться):
\begin{MyList}
  \item $g^{p-1} = 1$
  \item $g^{(p-1)/q} \neq 1~\forall q\colon q~\text{делит}~(p-1)$
\end{MyList}

Другой подход:
пусть у нас есть алгоритм, использующий первообразный корень, который за $A(n)$ умеет решать какую-то полезную задачу, а за $B(n)$ умеет проверять ответ на верность. Запустим его, скажем $\ln_p e \cdot 20$ раз на случайных числах, и получим верный ответ с вероятностью $1-e^{-20}$.

Если $p$ маленькое, то можно подсчитать корень заранее и забить константу в алгоритм.

