\input{ca_preamble.tex}

\begin{document}

\lectitle{6}{������� ���������. ���� �������-���������}
\lecauthor{�.\,�������}
\date{25 ������� 2008}
\maketitle

\tableofcontents

\section{�����������}
%����������� 1:
\begin{definition}
\label{PseudoPrimeNumber}
����� $n$ ���������� {\em ������������� �� ���������} $a$ $(1<a<n)$, ���� $\GCD (a,n)=1$ � $a^{n-1}\equiv 1 \pmod{n}$.
\end{definition}

%����������� 2: 
\begin{definition}
\label{KarmikleNumber}
{\em ����� ���������} --- ��������� �����, ������������� �� ������ ��������� $a$, ������� �������� � ��������.
\end{definition}

\begin{example}
����� ���������: $561=3\cdot 11\cdot 17$; $1105=5\cdot 13\cdot 17$
\end{example}

\begin{definition}
\label{ZGroup}
����� ��������� �����������: ${\ZZ}^*_n$ - ����������������� ������ ������� �������������� � $n$ � ������ ������� ${\ZZ}_n$.
\end{definition}

\section{������� ���������}

\begin{theorem}[��������, 1912]
\label{KarmikleTheorem}
����� $n$ --- �������� ���������, �����:
\begin{enumerate}
	\item[\rm 1.] ���� $n \div p^2$, ��� $p$ --- �������, �� $n$ --- �� ����� ���������;
	\item[\rm 2.] ���� $n = p_1 \cdot p_2 \cdot \cdots \cdot p_k$, ��� $p_i\neq p_j$ ��� $i \neq j$, �� ��� ����, ����� 
	$n$ �������� ������ ��������� ���������� � ����������, ����� $(n-1) \div (p_i-1)$  $(i=\overline{1,\,k})$;
	\item[\rm 3.] ���� $n = p_1 \cdot p_2 \cdot \cdots \cdot p_k$, ��� $p_i\neq p_j$ ��� $i \neq j$ � $n$ --- ����� ���������, �� $k \geq 3$.
\end{enumerate}
\end{theorem}

\begin{proof}
� �������������� �� ����� ������������ ������ (�������� ������):

\begin{theorem}[�����]
\label{Gauss}
${\ZZ}^*_n$ �������� ����������� ������� ����� � ������ �����, ����� $n=2,\, 4,\, p^m,\, 2\cdot p^m$, ���  $m\geq 1$, � $p$ --- ������� ��������.
\end{theorem}

%\textbf{�������������� ������� ���������:}
�������������� ������� ���������:

\begin{enumerate}
	\item ������������� ����������� 1.
	
		����� $n=p^t\cdot m$, $t\geq 2$, $p$ --- �������, $p\geq 2$

		�� ���������� �������, ��� $n$ --- �� ����� ���������.

		����� $n$ --- ����� ���������.

		�����, �� ����� \Ref{Gauss}
		� ������ ${\ZZ}^*_{p^2}$ ���� ����������� �������. ��������� ��� ����� $a$.

		��������� $ord_{p^2}\, a$ ������� �������� $a$ ��$\mod p^2$.

		$ord_{p^2}\, a = p\cdot (p-1)$ (��� �����, ������ ��� $\left|{\ZZ}_{p^2}^*\right| = p\cdot (p-1)$, � ${\ZZ}_{p^2}^*$ ����� ��� ������ �� ������ $p^2$, ����� $0,\,p,\,2\cdot p,\, \ldots ,\, (p-1)\cdot p$)

		�������, ��� $n$ �� �������� ������������� �� ��������� $a$.

		����� �� ���. ����� $n$ �������� ������������� �� ��������� $a$, �.�. ${a^{n-1}} \equiv 1 \pmod {n} \Rightarrow a^{n-1}\equiv 1 \pmod {p^2}$ (�� ����������� (���. \ref{PseudoPrimeNumber}))

		� ������ ������� $ord_{p^2}\, a = p \cdot (p-1) \Rightarrow a^{p(p-1)}\equiv 1 \pmod {p^2}$ (�� ����������� ������������ ��������)

		�� ����� �������, ��� $(n-1) \div p(p-1) \Rightarrow n \not\!\div p$.

		�������� ������������. ����� �������, $n$ --- �� �������� ������������� ������ �� ��������� $a$. 
		������������� $n$ --- �� ����� ���������, ��� � ����������� ��������.

	\item ������������� ����������� 2.
	
		\begin{enumerate}
			\item ������� ������ ����� ����������� --- �������������.
			
			����: 
			
			\begin{itemize}
			
			\item  $n = p_1\cdot p_2\cdot \cdots \cdot p_k$, ��� $p_i$ --- ������� �����, $p_i\neq p_j$ ��� $i\neq j$
			
			\item  $(n-1)\div (p_i-1)$
			
			\end{itemize}
			
			��������: $n$ --- ����� ���������.
			
			��������������:
			
			$(n-1)\div (p_i-1) \Rightarrow \exists m_i: n-1=m_i \cdot (p_i-1)$, ����� $\forall a\colon \GCD(a,n)=1,\, 1<a<n \Rightarrow a^{n-1}=(a^{p_i-1})^{m_i}\equiv 1 \pmod{p_i}$ (�� ������� �����).
			
			�� ��������� ������� �� ��������: $a^{n-1}\equiv 1 \pmod{n}$, ��� $n = p_1\cdot \cdots \cdot p_k$.
			
			����� �������, $n$ --- ����� ��������� (�� ����������� \ref{KarmikleNumber}), ��� � ����������� ��������.
			
			\item ������� ������ ����� ����������� --- �������������.
			
			����: 
			
			\begin{itemize}
			
			\item  $n = p_1\cdot p_2\cdot \cdots \cdot p_k$, ��� $p_i$ - ������� �����, $p_i\neq p_j$ ��� $i\neq j$
			
			\item  $n$ --- ����� ���������.
			
			\end{itemize}
			
			��������: $(n-1)\div (p_i-1)$
			
			��������������:
						
			���������� ����������� ������� � ������ $\ZZ^*_{p_i}$ $a_i\colon ord_{p_i}\,a_i = p_i-1$ (��� �����, ��� ��� $p_i$ --- ������� �����).
			
			$a^{n-1}_i\equiv 1\pmod{n}\Rightarrow (n-1)\div(p_i-1)$ ��� ���� $i$, ��� � ����������� ��������.
		\end{enumerate}
		
	\item ������������� ����������� 3.
	
	$k\neq 1$ --- �� ����������� \ref{KarmikleNumber} (��� ��� ����� ��������� --- ���������).
	
	����� $k = 2$. ����� $n = p\cdot q$, ��� $p$, $q$ --- ������� �����.
	
	����� $p<q$. $n-1 = p\cdot (q-1)+p-1\equiv (p-1)\pmod{(q-1)}\Rightarrow (n-1)\not\!\div (q-1)$ (��� ��� $p<q$).
	
	�������� ������������ � ������������ 2 ������ �������. ������ $k\neq 2$.
	
	����� �������, ��������, ��� $k\geq 3$, ��� � ����������� ��������.
\end{enumerate}

�������������� ������� ���������.
\end{proof}

\begin{corollary}
����� ��������� ���������� �����.
\end{corollary}

\section{���� �������--���������}

%���� �������� ������� � 1976 ����.

\begin{theorem}
����� $n$ --- ��������. 
����� ��� ����, ����� $n$ ���� ������� ���������� � ����������, ����� ��� ������� 
$a\in \ZZ^*_n$ ���� ��������� $a^{\frac{n-1}{2}}\equiv \left(\frac{a}{n} \right)\pmod{n}$.
\end{theorem}

\begin{proof}
������������� ������� �� �������� ������ ��� ������� ��������.

������� ������������� ������� �� ����������.
	
	����� $\forall a\in {\ZZ}^*_n\colon $ $a^{\frac{n-1}{2}}\equiv \left(\frac{a}{n}\right)\pmod{n}$, �� $n$ --- ���������.
	
	$a^{n-1} = (a^{\frac{n-1}{2}})^2\equiv \left(\frac{a}{n}\right)^2\pmod {n}$
	
	$\left(\frac{a}{n}\right)^2 = 1\Rightarrow a^{n-1}\equiv 1\pmod{n}$
	
	����� �������, $n$ --- ����� ��������� (�� ����������� \ref{KarmikleNumber}).
	
	�������������, $n=p_1\cdot p_2\cdot \cdots \cdot p_k$, ��� $p_i$ --- ������� �����, $i=\overline{1{, }k}$ (�� ������� \Ref{KarmikleTheorem})
	
	���������� $b$ �����, ��� $\left(\frac{b}{p_1}\right)\equiv -1\pmod{n}$
	
	������ ����� $a$, ���:
$$	
	\left\{	
		\begin{aligned}
		a&\equiv b\pmod{p_1}\\
		a&\equiv 1\pmod{p_i},\quad i = \overline{2{,}k}\\
		\end{aligned}
	\right.	
$$	
����� $a$ ���������� �� ��������� ������� �� �������� � ����������� ${\ZZ}^*_n$ (��� ��� ������� ������ � $n$).
	
$	\biggl(\dfrac{a}{n}\biggr)=\left(\dfrac{a}{p_1}\right)\cdot \underbrace{\left(\frac{a}{p_2}\right)\cdot \cdots \cdot \left(\frac{a}{p_k}\right)}_{1} = \biggl(\dfrac{a}{p_1}\biggr) = \biggl(\dfrac{b}{p_1}\biggr) = -1$

$a^{\frac{n-1}{2}}\equiv \left(\frac{a}{n}\right)\pmod{n}$

$\left(\frac{a}{n}\right)=-1 \Rightarrow a^{\frac{n-1}{2}}\equiv -1\pmod{n}$

$a^{\frac{n-1}{2}}\equiv \left(\frac{a}{n}\right)=-1\pmod{p_1}$

$a^{\frac{n-1}{2}}\equiv \left(\frac{a}{n}\right)=-1\pmod{p_2}$ (������������ � ���, ��� $a\equiv 1\pmod{p_i}$ $i=\overline{2{, }k}$)

������, ������� ���� ������������� � ���, ��� $n$ --- ���������.
\end{proof}

\begin{definition}\label{EilerPseudoPrimeNumber}
�������� ��������� ����� $n$, ��� ������� $a^{\frac{n-1}{2}}\equiv \left(\frac{a}{n}\right)\pmod{n}$ ��� �������������� $a$ ���������� 
{\em ���������� �������������� ������� �� $\mod a$}.
\end{definition}

\section{�������� �������-���������}

\begin{algorithmic}[1]
\REQUIRE $n$ --- �������� �����

\ENSURE ��������� � ���������� ��� ��������� �������� �����

\FOR{$i = 1,\ldots ,k$}

\STATE $a := rand(2{, }\ldots {, }n-1);$

\IF{$\GCD (a, n)>1$}

\STATE PRINT `n --- ���������';

\STATE RETURN;

\ENDIF

\IF{$a^{\frac{n-1}{2}}\not\equiv \frac{a}{n}$}

\STATE PRINT `n --- ���������';

\STATE RETURN;

\ENDIF

\ENDFOR

\STATE PRINT `n --- �������� �������'
\end{algorithmic}

����������� ������, ���� ����� ����� `�������� �������', �� ����������� $\left(\frac{1}{2}\right)^k$

\begin{theorem}
����� $n$ --- �������� ���������. �����

\begin{enumerate}
	\item ���� $n$ --- �������� ������������� �� ��������� $a\in {\ZZ}_n^*$, �� ��� ������������� �� ��������� $a$;
	
	\item ���� $n$ --- �������� ������������� �� ���������� $a,\, b\in {\ZZ}_n^*$, ����� $n$ --- �������� ������������� �� ���������� $a\cdot b$ � $a\cdot b^{-1}$;
	
	\item $E_n = \left\{ a\in {\ZZ}_n^* \colon a^{\frac{n-1}{2}}\equiv \left(\frac{a}{n}\right)\pmod{n} \right\}$ --- ��������� � ${\ZZ}^*_n$;
	
	\item ���� $n$ �� �������� ��������� ������������� �� ������-���� ���������, ����� $\left| E_n \right| \leq \frac{1}{2} \left| {\ZZ}_n^* \right|$.
\end{enumerate}
\end{theorem}

\end{document}