\Section{Теория чисел}{10 июня}{Илья Ольховский}
 \Subsection{Китайская теорема об остатках}
 
  Из алгебры известно, что если $a_1, \ldots, a_k$ - попарно взаимно простые числа, $\forall i\; \alpha_i\ge 1$, то
   $$\mathbb{Z}/(a_1\cdot \ldots a_k) \simeq \mathbb{Z}/a_1 \oplus \ldots \oplus \mathbb{Z}/a_k)$$
   
     Нам интересно взять не абы какие взаимно простые числа, а различные простые. Выражение можно переписать попроще так:
     $$\forall x\in \mathbb{Z}:\;\; x \bmod (p_1\cdot \ldots \cdot p_k) \simeq (x \bmod p_1, \ldots, x\bmod p_k)$$
     
     Или, если словами, остаток от деления любого числа $x$ на произведение простых чисел однозначно определяется остатками от деления $x$ на каждое из этих чисел.
     
      Этот знаменательный факт даёт нам возможность производить вычисления, не влезая по уши в длинную арифметику. Например, если мы знаем, что результат вычислений не превосходит, скажем, $10^{1000}$, достаточно взять 112 простых, больших $10^9$ и считать остатки по каждому из простых по отдельности.

       Научимся восстанавливать число по его остаткам на различные простые. Ясно, что достаточно научиться восстанавливать для двух модулей, то есть по остаткам от деления на $m_1$ и $m_2$ получать остаток от деления на $m_1m_2$. Для большего числа модулей - берём первые два, схлопываем в один и так далее. Итак:
       $$x\equiv a_1 \pmod {m_1}$$
       $$x\equiv a_2 \pmod {m_2}$$
        Мы хотим подобрать такие $e_1$ и $e_2$, что 
        $$e_1 \equiv 1 \pmod {m_1}\qquad e_1 \equiv 0 \pmod {m_2}$$
        $$e_2 \equiv 0 \pmod {m_1}\qquad e_2 \equiv 1 \pmod {m_2}$$        
        Тогда $x\equiv a_1e_1+a_2e_2 \pmod{m_1m_2}$. Нам подойдут такие:

        $$e_1=m_2\cdot (m_2^{-1}\pmod{m_1})\qquad e_2=m_1\cdot (m_1^{-1}\pmod{m_2})$$ 
	Так же советую почитать про алгоритм Гарнера.
	
	 Сравним времена работы длинной арифметики и арифметики на остатках. Пусть $T$ - кол-во операций, $n$ - длина промежуточных вычислений, $m$ - длина результата. 
	 \begin{enumerate}
	 	\item Длинка: $T\cdot n\log n$
	 	\item Остатки (нам понадобится порядка $m$ различных модулей): $T\cdot m + m^2\log n$
	 \end{enumerate}
	\Subsection{Решето Эратосфена}
	
	 Решето за $\mathcal{O}(n\log \log n)$:
	 \begin{verbatim}
	 for(int i = 2; i < n; ++i)
         if (!is[i])
	         for(int j = i * i; j < n; j += i) is[j] = true; //не простое
     \end{verbatim}    
      Решето за $\mathcal{O}(n)$. Пусть $d[x]$ - минимальный делитель $x$, больший 1. Тогда;
      
      $\forall x:\;x=d[x]\cdot y$. Если $x$ - не простое, то $y>1$, и $d[y]\ge d[x]$.
      \begin{verbatim}
      for(int y = 2; y < n; ++y){
          if (d[y] == 0)
             d[y] = y, primes.push_back(y);
          for(int i = 0; p[i] <= d[y] && y*p[i] <= n; ++i)
              d[p[i]*y] = p[i];
	  }
	  \end{verbatim}
	   Почему линия? Во внутреннем $for$ выражение $p[i]*y$ каждый раз новое (любое число $x$ однозначно представляется в виде $d[x]*y$), а всего их $n$.
	   \Subsection{Вычисление мультипликативных функций}
	   
	    Функция наз-ся мультипликативной, если:
	    $$gcd(a, b)=1 \rightarrow f(ab)=f(a)f(b)$$. Пусть нам надо вычислить $f(1), \ldots, f(n)$. Естественная динамика: пусть $x=\sqcap p_i^{\alpha_i}$, тогда:
	    $$f(x)=f(\frac{x}{p_1^{\alpha_1}})\cdot f(p_1^{\alpha_1})$$
	    
	     Особого внимания заслуживает функция эйлера:
	     $$\varphi(x)=x\cdot \sqcap\frac{p_i-1}{p_i}$$
	      Пусть $y=x/d[x]$. Тогда $\varphi(x)$ удобно считать так:
	      $$\varphi[x]=\varphi[y]\cdot(d[y]==d[x] ? d[x] : d[x] - 1)$$
	     \Subsection{Простые числа}
	     
	      \textbf{Генерация}. Поскольку простые числа распределены достаточно плотно, чтобы получить большое простое, берём случайное большое число и прибавляем к нему 1, пока оно не станет простым. 
	      
	      \textbf{Проверка на простоту}
	      \begin{enumerate}
	      	\item В лоб - $\sqrt{x}$. Просто ищем делитель тупым перебором.
	      	\item Если много запросов, можно предпосчитать простые числа за$\sqrt{x}$ и на запросы отвечать уже за $\frac{\sqrt{x}}{\log x}$, итерируясь только по простым.
	      	\item Тест Ферма. Берём случайное $a$ и проверяем, что $a^{x-1}\equiv 1\pmod x$. Числа, удовлетворяющие условию, образуют подгруппу в группе обратимых элементов $x\mathbb{Z}$ (взаимно простые). Если это собственная подгруппа, её размер не более $\frac{\varphi(x)}2$ по теореме Лагранжа. Поэтому вероятность ошибиться не более $\frac12$. Если же подгруппа совпадает со всей группой (но число не простое), то нам не повезло. Это значит, мы наткнулись на одно из чисел Кармайкла, для которых тест Ферма не работает (мы всё ещё можем наткнуться на число, не взаимно простое с $x$, но таких обычно мало).
	      	
	      	 Можно доказать, что у любого числа Кармайкла хотя бы три делителя. Это даёт нам алгоритм проверки на простоту за $\sqrt[3]{x}$. Сначала проверяем, что нам не подсунули число Кармайкла (у него есть делитель $\le \sqrt[3]{x}$), потом запускаем тест Ферма.
	      	 
	      	 \item Тест Миллера-Рабина. Этот тест уже всегда работает (мы не доказывали). $a$ нужно брать случайным, но по какой-то гипотезе можно взять одно из первых $\log^2x$ или что-то вроде того. 
	      	 $$x-1=2^s\cdot t$$
	      	 Алгоритм:
	      	 \begin{verbatim}
	      	 a=a^t
	      	 FOR i = 1...s
	      	    if a^2=1 && |a|!=1
	      	        NOT PRIME
	      	    a=a^2
	      	 return a==1 ? PRIME : NOT PRIME
	      	 \end{verbatim}
	      	 \end{enumerate}
	      	 
	      	 \Subsection{Факторизация}
	      	 
	      	 Задача: по числу $n$ либо сказать, что оно простое, либо представить его в виде произведения двух множителей (каждый больше 1).

	      	  Уже умеем  за $\sqrt{n}$ и $\sqrt{n}/\log n$ с предподсчётом. Оказывается, можно и быстрее.
	      	  
	      	  \textbf{Эвристика Полларда}
	      	   Пусть $f:[0\ldots n-1] \to [0\ldots n-1]$ - некоторая случайная функция (подходит $f(x)=(x^2 + 3)\bmod n$. Без док-ва).
	      	   
	      	    Возьмём случайное $a$ и рассмотрим цепочку: $\{x_i\}:\;a, f(a), f(f(a)), \ldots$. Она должна зациклиться примерно через $\sqrt{n}$ шагов. Вероятность того, что зациклится сильно раньше или позже очень низкая.
	      	    
	      	     Пусть $n=pq\; p\le q, p>1$ и $y_i=x_i\bmod p$. Последовательность $y_i$ должна зациклиться примерно через $\sqrt{p}\le \sqrt[4]{n}$ шагов. Значит в некоторый момент случится так, что:
	      	     $$x_i\equiv x_{i+T}\pmod p \qquad x_i\not\equiv x_{i+T}\pmod n$$
	      	     
	      	      Значит $gcd(x_{i+T}-x_i, n)\ge p$, и $gcd(x_{i+T}-x_i, n)\neq n$, т.е. $gcd$ - некоторый нетривиальный делитель $n$. Это как раз то, что нам надо. Итак, код:
	      	      \begin{verbatim}
	      	      a = RANDOM
	      	      b = f(a)
	      	      while (true){
	      	          a = f(a)
	      	          b = f(f(b))
	      	          x = gcd(b - a, n)
	      	          if x != 1 return x
	      	      \end{verbatim}
	      	       Асимптотика - $\mathcal{O}(\sqrt[4]{n}\cdot gcd)$. На практике даже приемлемо работает.
	      	          