\documentclass{article}
\usepackage[cp1251]{inputenc}
\usepackage[russian]{babel}
\usepackage[dvips,a4paper,margin=3cm]{geometry} 
%\usepackage[T2A]{fontenc}                                %This should be compiled with pdflatex
%\usepackage[unicode,a4paper,pdftex,colorlinks]{hyperref} %This should be compiled with pdflatex
\usepackage{amssymb}
\usepackage{amsmath}

\usepackage{amsthm}
\theoremstyle{plain}
\newtheorem{theorem}{Теорема}
\newtheorem{proposition}{Утверждение}
\newtheorem{lemma}{Лемма}
\newtheorem{corollary}{Следствие}
\newtheorem{property}{Свойство}
\theoremstyle{remark}
\newtheorem{definition}{Определение}
\newtheorem{note}{Замечание}
\newtheorem{example}{Пример}
\newtheorem{exercize}{Упражнение}

\usepackage[noend]{algorithmic}
\def\algorithmicrequire{\textbf{Вход:}}
\def\algorithmicensure{\textbf{Выход:}}
\def\algorithmiccomment#1{\quad// {\sl #1}}

\usepackage[bf,small,raggedright,indentafter]{titlesec} 
\titlelabel{\thetitle. } 

\usepackage{tocloft}
\renewcommand{\cftsecaftersnum}{.}
\renewcommand{\cftsubsecaftersnum}{.}

\usepackage[format=hang,labelsep=period,font={small},labelfont={it}]{caption}

\newcommand{\lectitle}[2]{\title{Лекция \No\,#1 \\ #2}}
\newcommand{\lecauthor}[1]{\author{Лектор: Н.Ю.\,Золотых \hspace{0.2\textwidth} Записал: #1}}

\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\Ref}[1]{{\rm(\ref{#1})}}
\newcommand{\GCD}{\mathop{\mbox{\rm НОД}}}
\newcommand{\divv}{\mathop{\,\mbox{\raisebox{-.45ex}[0pt]{$\vdots$}}\,}}

\newenvironment{narrowarray}[1]{\arraycolsep=0.15em\begin{array}{#1}}{\end{array}}

\begin{document}
\title{Обоснование теста Миллера--Рабина \\для проверки простоты чисел}
\date{Записал Дм. Потапов}
\maketitle


\section{Свидетели простоты}

Пусть $n \in N$, где $n$ --- нечётно, тогда $n$ можно представить в виде:
\begin{equation}
n-1=2^{s}t
\label{n_minus_1}
\end{equation}
где $t$ --- также нечётно.
\begin{definition}
Число $1<b<n$ назовём {\em свидетелем простоты} числа $n$, если $n$ --- сильно псевдопростое по основанию $b$, т.\,е. $\GCD (b,n)=1$ и выполняется
\begin{equation}
b^t \equiv 1 \pmod{n}
\end{equation}
или
\begin{equation}
\exists k\in\{1,\dots,s-1\}: b^{2^{k}t} \equiv -1 \pmod{n}
\end{equation}
\end{definition}
Множество всех свиделелей простоты числа $n$ обозначим $B$. 
Здесь и далее будем предполагать что $n$ нечётно и не кратно трём.

\section{Лжесвидетели}

\begin{definition}
Число $a \in Z_{n}^{*}$ назовем {\em лжесвидетелем}  числа $n$ если выполняется одно из следующих условий:

1) $a^{n-1}\not\equiv 1\pmod{n}$

2) $a^{k}\not\equiv-1\pmod{n}, \forall k \in N$ и для некоторого простого числа $p$, такого что $n$ делится на него без остатка, порядок $a$ по модулю $p$ равен $p-1$ (т.\,е. $\forall k \in \{1,\dots,p-2\}: a^{k}\not\equiv 1\pmod{n}, a^{p-1}\equiv 1\pmod{n}$)
\end{definition}

Множество всех лжесвиделелей числа $n$ обозначим $A$.

\section{Теорема Рабина}

\begin{lemma}
\label{proizvedenie}
Произведение лжесвидетеля и свидетеля простоты не является свидетелем простоты, т.\,е.
\begin{equation}
a \in A, b \in B \Rightarrow ab\pmod{n}\notin B \Rightarrow B\cap aB = \emptyset
\end{equation}
\end{lemma}
\begin{proof}
Рассмотрим два случая: 
\par{1) Пусть $a^{n-1}\not\equiv 1\pmod{n}$, тогда: $(ab)^{n-1}\not\equiv b^{n-1}\pmod{n}$, но по определению свидетеля $b^{n-1}\equiv 1\pmod{n}$, т.\,е. $(ab)^{n-1}\not\equiv 1\pmod{n}$, следовательно $ab\pmod{n}\notin B$ }
\par{2) Пусть теперь $a^{n-1}\equiv 1\pmod{n}$ и $\exists p$ --- простой делитель $n$ и порядок $a$ по модулю $p$ равен $p-1$  и $a^{k}\not\equiv-1\pmod{n}, \forall k \in N$ }
\par{Воспользуемся формулой (\ref{n_minus_1}). Рассмотрим минимальное $k\in\{1,\dots,s-1\}: a^{2^{k}t} \equiv 1 \pmod{n}$, так как $p$ --- делитель $n$, то $a^{2^{k}t} \equiv 1 \pmod{p}$, а так как $a$ имеет порядок $p-1$ по модулю $p$, то $2^{k}t$ должно делиться на $p-1$ без остатка.}
\par{так как $t$ --- нечётно, а $p-1$ --- чётно, то $2^{k}t\ne t \Rightarrow k\ge 1\Rightarrow a^{t}\not\equiv 1\pmod{p}\Rightarrow a^{t}\not\equiv 1\pmod{n}$ }
\par{Воспользуемся исходными данными: НОД$(b,n)=1$, и $n$ делится на $p\Rightarrow$НОД$(b,p)=1$. Для всех $j: k\le j\le s, 2^{j}t$ делится на $p-1$, по малой теореме Ферма будем иметь:}
\begin{equation}
b^{2^{j}t}\equiv 1\pmod{p}\Rightarrow b^{2^{j}t}\not\equiv-1\pmod{n}
\end{equation}
\begin{equation}
b \in B\Rightarrow b^{2^{j}t}\equiv1\pmod{n},~\forall j: k\le j\le s\mbox{ i }b^{2^{k-1}t}\equiv\pm 1\pmod{n}
\end{equation}
Отсюда имеем:
\begin{equation}
(ab)^{2^{j}t}\equiv b^{2^{j}t}\equiv 1\pmod{n},~\forall j: k\le j\le s
\end{equation}
и
\begin{equation}
(ab)^{2^{k-1}t}\equiv\pm a^{2^{k-1}t}\not\equiv\pm 1\pmod{n}
\end{equation}
\begin{equation}
(\mbox{Так как } a^{2^{k-1}t}\not\equiv 1\pmod{n}\mbox{ и }a^{k}\not\equiv-1\pmod{n}, \forall k \in N)
\end{equation}
Следовательно $ab$ не является свидетелем простоты числа $n$.
\end{proof}
\begin{lemma}
\label{group_izomorphy}
Пусть $n$ --- нечётное число, число $n$ --- простое и $n$ делится на $p^2$ без остатка, тогда множество
\begin{equation}
\{1+kn/p, k=0,\dots,p-1\}
\end{equation}
образует подгруппу в $Z_{n}^{*}$ порядка $n$ и все элементы за исключением единицы имеют порядок $n$.
\end{lemma}
\begin{proof}
Возьмем любые два элемента из данной подгруппы и перемножим их:
\begin{equation}
(1+kn/p)(1+k'n/p)=1+(k+k')n/p+kk'n^{2}/p^{2}\equiv 1+(k+k')n/p\pmod{n}
\end{equation}
т.\,е.
\begin{equation}
(1+kn/p)(1+k'n/p)\equiv 1+(k+k')n/p\pmod{n}
\end{equation}
Из  этого равенства видно что данная подгруппа изоморфна циклической группе порядка $n$.
\end{proof}
\begin{lemma}
\label{peresechenie}
Пусть $a, b \in Z_{n}^{*}, a\ne b$, тогда $Ba\cap Bb = \emptyset \iff B\cap Bab^{-1} = \emptyset$ 
\end{lemma}
\begin{proof}
Очевидно. Отображение $x \mapsto xa$ задаёт взаимно однозначное соответствие между $B$ и $Ba$. множества $B$ и $Ba$ равномощны и целиком содержатся в $Z_{n}^{*}\mbox{ }(a \in Z_{n}^{*})$.
\end{proof}
\begin{lemma}
\label{delenie}
Пусть $n$ делится на $p^2$ ($p$ --- простое), тогда мощность множества $B$ не превосходит $\frac{\phi(n)}{p}$. 
\end{lemma}
\begin{proof}
Рассмотрим группу $G=\{1+kn/p, k=0,\dots,p-1\}$ из Леммы \ref{group_izomorphy}, так как $n$ делится на $p$, следовательно $n-1$ на $p$ не делится, следовательно $\forall a \in G (a\ne 1): a^{n-1}\not\equiv 1\pmod{n}$, что означает что $a$ --- лжесвидетель. 
По Лемме \ref{proizvedenie}, $B\cap Ba = \emptyset$, воспользуемся Леммой \ref{peresechenie}:
\begin{equation}
\forall g_1,g_2\in G, g_1\ne g_2: B \cap B{g_2}g_1^{-1} = \emptyset~(a \mbox{ обозначили как }{g_2}g_1^{-1}) \Rightarrow Bg_1\cap Bg_2 = \emptyset
\end{equation}
Все $Bg$ содержатся в $Z_{n}^{*}$, а значит и их объединение тоже, следовательно:
\begin{equation}
\Big | \bigcup_{g\in G} Bg\Big |\le\vert Z_{n}^{*}\vert = \phi(n)
\end{equation}
Но все $Bg$ попарно не пересекаются и равномощны, а значит:
\begin{equation}
\Big | \bigcup_{g\in G} Bg\Big |=p\vert B\vert\le\phi(n)\Rightarrow\vert B\vert\le\frac{\phi(n)}{p}
\end{equation}
\end{proof}

\begin{lemma}[Теорема Рабина] Пусть $n$ свободно от квадратов, тогда мощность множества $B$ не превосходит $\frac{\phi(n)}{4}$. 
\end{lemma}
\begin{proof}
Пусть $p_1, p_2,\dots, p_k$ --- все простые делители $n$, ($3<p_k<\dots<p_2<p1,~k\ge 2$). Пользуясь китайской теоремой об остатках и теоремой о существовании первообразного элемента выберем $a_1$ и $a_2$ ($a_1\ne a_2$) такие что 

$a_1\equiv 1\pmod{p_2},~a_1\equiv 1\pmod{p_3},\dots,~a_1\equiv 1\pmod{p_k},~ord_{p_1}a_1=p_1-1,$

$a_2\equiv 1\pmod{p_1},~a_2\equiv 1\pmod{p_3},\dots,~a_2\equiv 1\pmod{p_k},~ord_{p_2}a_2=p_2-1$. 

Заметим что:
\begin{equation}
a_i\equiv 1\pmod{\frac{n}{p_i}}\Rightarrow\forall j \in N: a_i^j\equiv 1\pmod{\frac{n}{p_i}}\Rightarrow\forall j \in N: a_i^j\not\equiv -1\pmod{n}
\end{equation}
Значит $a_1$, $a_2$ --- лжесвидетели. Рассмотрим два случая: 

$k=2$: если для некоторого $j:~(a_1a_2)^j\equiv 1\pmod{n}\Rightarrow (a_1a_2)^j\equiv 1\pmod{p_1}\Rightarrow a_1^j\equiv 1\pmod{p_1}\Rightarrow j$ делится на $p_1-1$. $n-1$ не делится на $p_1-1$ (так как $n-1=p_2(p_1-1)+p_2-1, p_2<p_1$), следовательно $(a_1a_2)^{n-1}\not\equiv 1\pmod{n}$, а значит $a_1a_2$ --- третий лжесвидетель.

$k\ge 3: a_1a_2\equiv 1\pmod{\frac{n}{p_1p_2}}\Rightarrow\forall j \in N: (a_1a_2)^j\equiv 1\pmod{\frac{n}{p_1p_2}}\Rightarrow\forall j \in N: (a_1a_2)^j\not\equiv -1\pmod{n}$, а значит $a_1a_2$ --- снова третий лжесвидетель.

Итак, у нас есть три различных лжесвидетеля, применим лемму \ref{peresechenie}: группы $B, Ba_1, Ba_2 \mbox{ и } Ba_1a_2$ попарно различны, равномощны, попарно не пересекаются и целиком содержатся в $Z_{n}^{*}$, а значит:
\begin{equation}
\vert B\cup Ba_1\cup Ba_2\cup Ba_1a_2\vert =4\vert B\vert\le Z_{n}^{*}=\phi(n)
\end{equation}
т.\,е. $\vert B\vert\le\frac{\phi(n)}{4}$  что и требовалось доказать. 
\end{proof}
\end{document} 
