\input{ca_preamble.tex}


\begin{document}

\lectitle{4}{���������� ����������� ����� � ���� �������}
\lecauthor{�.\,���������, �.\,���������}
\date{4 ������� 2008}
\maketitle


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

����� $p$ --- �������� ������� �����. ��������� ����� $x$ �����, ���:
\begin{equation}\label{eq:_1}
x^2\equiv a \pmod p
\end{equation}

��� ��� $p$ --- ��������, �� ���������� �������� ����� $s$, ����� ���:
\begin{equation}\label{eq:_2}
p-1=2^{\alpha }\cdot {s}
\end{equation}

����� ��� �������� ��������� ������������ ������� $n$. �������� $b$, ���
\begin{equation}\label{eq:_3}
b = n^s\pmod p
\end{equation}
\begin{note}
$b$ ����������� �� $\log s$.
\end{note}

���������� 2 ������: $p\equiv 1\pmod 4$ � $p\equiv 3\pmod 4$.

\begin{itemize}
    \item[1)] $p\equiv 3\pmod 4$. � �������� $x$ ����� $a^{\frac{p+1}{4}}$. ��������, ��� � ���� ������ ��������� (\ref{eq:_1}) ����� ���������, �.�. $a^{\frac{p-1}{2}}\equiv 1\pmod p$ (��� ������� �� ����, ��� $a$-�����).
  \item[2)] $p\equiv 1\pmod 4$. ���������� ����� $r=a^{\frac{s+1}{2}}$. ��� ����� � ��������� ������ ������ � $x$, � ������:
\end{itemize}

\begin{proposition}
 $(a^{-1}r^2)^{2^{\alpha-1}}\equiv 1\pmod p$.
\end{proposition}

\begin{proof}
$$ (a^{-1}r^2)^{2^{\alpha-1}} = (a^s)^{2^{\alpha -1}} =a^{s\cdot 2^{\alpha-1}}=a^{\frac{p-1}{2}}\equiv1\pmod p,
 \mbox{ ��� ��� } p\equiv1\pmod 4$$
\end{proof}

����� ��������� �������� $x = \sqrt{a}$ ���� ���������� $r$ �� ��������� ������ ������� $2^{\alpha}$ �� 1.

\begin{proposition}
$b$ --- ������������� ������ �� 1 ������� $2^{\alpha}$.
\end{proposition}

\begin{proof}
��� �������������� ������� ����������� ���� ��������:

a) $b$ --- ������ �� 1 ������� $2^{\alpha}$. �������������, $b^{2\alpha} = n^{s\cdot 2^{\alpha}}=n^{p-1}=1$.

�) $b$ --- ������������� ������. �����������, ��� ��� �� ���. �����:
\begin{equation}\label{eq:_4}
\exists j<2^{\alpha} : b^{j}\equiv 1\pmod p
\end{equation}
��������, ��� ���������� ����������������� �� $j$, ������� �������� ���������� ����� $2^{\alpha}$. ���� �� ���, �� �� ������ ������ ����� $t<j: b^{t}\equiv 1\pmod p$, ������ $t$ ����� �������� ���������  $2^{\alpha}$. �������������:
$$ 2^{\alpha} = k\cdot j + t,\qquad 0<t<j$$
$$ b^{2^{\alpha}} = b^{k\cdot j} + b^{t}$$
��� ��� $b^{2^{\alpha}} = 1$ � $b^{k\cdot j} = 1$, �� � $b^{t}=1$. ��������� ��� ��������� �� ��� ���, ���� $t$ --- �� ����� �������� ��������� $2^{\alpha}$.

����� ������:
$$ j = 2^{\beta}\qquad 0\leq \beta < \alpha $$
�� ����� ����������� �����������, ���������� $\theta : Z^{*}_{p} = \{1,\theta,\theta^2,\ldots, \theta^{p-2}\} $ � ��� ��� $n$ --- �������, �� $n = \theta^{2i+1}$. � ������ �������, �.�. $b^{j}\equiv 1\pmod p$, �� ���������� $k: b^{j} = \theta^{k\cdot p}$. �.�. �����:
$$ \theta^{k\cdot p} = b^{j} = (n^s)^{2^{\beta}} = \theta^{(2i+1)\cdot s \cdot 2^{\beta}}$$
������
$$ k \cdot p = k \cdot s \cdot 2^{\alpha} = (2i+1) \cdot s \cdot 2^{\beta}$$
$$ k \cdot 2^{\alpha - \beta} = 2i+1$$
�� � ����� ����� ����������� ����� ������ ����� (�.�. $\beta < \alpha$), � � ������ ��������! ������ ������������� (\ref{eq:_4}) �� �����, � $b$ --- ������������� ������ ������� $2^{\alpha}$ �� 1.
\end{proof}

����� ������ $x$ � ���� $x=b^{j}r$, ��� $b = n^{3}\mod p$, $r =
a^{\frac{s+1}{2}}\mod p$.

����� ����� $j$, ��� $(b^{j}r)^{2}\equiv a\pmod{p}$.

�������� $j$ ��������� � �������� ������� ����������:

\begin{equation} \label{eq1}
    j=j_{0}+2j_{1}+\ldots+2^{\alpha-2}j_{\alpha-2}, \mbox{ ��� }
    j_{k}\in\{0,1\}.
\end{equation}


\begin {proposition}
    $j<2^{\alpha-1}$
\end {proposition}

\begin{proof}
    \begin{multline*}
        \mbox{ ����� } j=j'+2^{\alpha-1} ,\mbox{ ����� ��������� } j \mbox{ � ��������� } (b^{j}r)^{2}\equiv a\pmod{p}
        \mbox{ �������: }\\
        \shoveleft{(b^{j'+2^{\alpha-1}}r)^{2}\equiv a\pmod{p} }\\
        \shoveleft{(b^{j'}b^{2^{\alpha-1}}r)^{2}\equiv a\pmod{p}} \\
        \shoveleft{b^{2^{\alpha}}\equiv 1\pmod{p} \Rightarrow (b^{j'}r)^{2}\equiv
        a\pmod{p}}.\\
    \end{multline*}
\end{proof}

��������� $j_{0},j_{1},\ldots,j_{\alpha-2}$ � ���������
(\ref{eq1}).

$$
    j_{0}\mbox{: } (r^{2}a^{-1})^{2^{\alpha-1}}\equiv 1\pmod{p}
    \Rightarrow (r^{2}a^{-1})^{2^{\alpha-2}}\equiv
    \begin{cases}
        1\pmod{p}\\
        -1\pmod{p}
    \end{cases}
    \Rightarrow \mbox{ �������� }
    \begin{cases}
        j_{0} = 0\\
        j_{0} = 1.
    \end{cases}
$$

\begin {proposition}
    $(b^{j_{0}}r)^{2}a^{-1}$ --- ������ ������� $2^{\alpha-2}$ �� 1.
\end {proposition}

\begin{proof}
    $$
        ((b^{j_{0}}r)^{2}a^{-1})^{2^{\alpha-2}}=(b^{j_{0}})^{2^{\alpha-1}}(r^{2}a^{-1})^{2^{\alpha-2}}\equiv
        1\pmod{p}.
    $$
\end{proof}

����� ������� $j_{0},j_{1},\ldots,j_{k-1}$, ����� ���
$$
    (b^{j_{0}+2j_{1}+\ldots+2^{k-1}j_{k-1}}r)^{2}a^{-1} -
    \text{ ������ ������� } 2^{\alpha-k-1} \text{ �� } 1.
$$

��������� $j_{k}$.

\begin{multline*}
    j_{k}\mbox{: }
    ((b^{j_{0}+2j_{1}+\ldots+2^{k-1}j_{k-1}}r)^{2}a^{-1})^{2^{\alpha-k-1}}\equiv
    1\pmod{p} \Rightarrow \\
    \shoveleft{\Rightarrow
    ((b^{j_{0}+2j_{1}+\ldots+2^{k-1}j_{k-1}}r)^{2}a^{-1})^{2^{\alpha-k-2}}\equiv
    \begin{cases}
        1\pmod{p}\\
        -1\pmod{p}
    \end{cases}
    \Rightarrow \mbox{ �������� }
    \begin{cases}
        j_{k} = 0\\
        j_{k} = 1.
    \end{cases}}
\end{multline*}

\begin {proposition}
    $(b^{j_{0}+2j_{1}+\ldots+2^{k}j_{k}}r)^{2}a^{-1}$ --- ������
    ������� $2^{\alpha-k-2}$ �� 1.
\end {proposition}

\begin{proof}
    \begin{align*}
        ((b^{j_{0}+2j_{1}+\ldots+2^{k}j_{k}}r)^{2}a^{-1})^{2^{\alpha-k-2}}=(b^{j_{k}})^{2^{\alpha-1}}((b^{j_{0}+2j_{1}+\ldots+2^{k-1}j_{k-1}}r)^{2}a^{-1})^{2^{\alpha-k-2}}\equiv
        1\pmod{p}.
    \end{align*}
\end{proof}

��� $k=\alpha-2$ ��������:

$$
    (b^{j_{0}+2j_{1}+\ldots+2^{\alpha-2}j_{\alpha-2}}r)^{2}a^{-1} -
    \text{ ������ ������� } 1 \text{ �� } 1.
$$

����� �������,
$b^{j_{0}+2j_{1}+\ldots+2^{\alpha-2}j_{\alpha-2}}r=x$, ��� $j_{i}$
($i=0, \ldots, \alpha-2$) ������������ �������� �������:
\begin{align*}
    ((b^{j_{0}+2j_{1}+\ldots+2^{i-1}j_{i-1}}r)^{2}a^{-1})^{2^{\alpha-i-2}}\equiv
    \begin{cases}
        1\pmod{p}\\
        -1\pmod{p}
    \end{cases}
    \Rightarrow
    \begin{cases}
        j_{i} = 0\\
        j_{i} = 1.
    \end{cases}
\end{align*}.

����� ������� �������� ��������� ��������:

\subsection*{�������� ������}

\begin{algorithmic}[1]

\REQUIRE $p$ - �������� ������� �����, $a$ - ����� ����� �� 0 �� $p-1$ (�����).
\ENSURE $x$ - ����� �����, ��������������� ������� $x^2\equiv a \ (mod \ p)$

\STATE ���� $p\equiv 3 \ (mod \  4)$, �� $x = a^{\frac{p+1}{4}}$. �����.

\STATE ���������� $p-1$ � ���� $p-1 = 2^\alpha \cdot s$, ��� $s$ - �������� ����������� �����.

\STATE ������ $n$ - ��������� ������������ �������.

\STATE ������� $b = n^s \ (mod \ p)$

\STATE ������� $r = a^{\frac{s+1}{2}}$

\FOR{$k = 0, \dots, \alpha-2$}

\STATE ����� $j_k$, ����� ��� $(b^{j_0+2j_1+ \dots + 2^k j_k} r)^2 a^{-1}$ - ������ ������� $2^\alpha - k - 2$ �� 1.
\ENDFOR

\STATE $x = b^{j_{0}+2j_{1}+\ldots+2^{\alpha-2}j_{\alpha-2}}r$. �����.

\end{algorithmic}

\begin{example}
    ����� ���������� ������ �� $a = 186$ �� ������ $p = 401$.
    \begin{multline*}
        \shoveleft{}\\
        \shoveleft{n = 3 \mbox{ --- ������� }}\\
        \shoveleft{p-1 = 2^{4}\cdot 25}\\
        \shoveleft{b\equiv n^{s}\pmod{p}\equiv 3^{25}\pmod{401} \equiv 268\pmod{401}}\\
        \shoveleft{r\equiv a^{s+1/2}\pmod{p}\equiv 186^{13}\pmod{401}\equiv
        103\pmod{401}}\\
        \shoveleft{a^{-1}\equiv 235\pmod{401}}\\
        \shoveleft{r^{2}a^{-1}\equiv 103^{2}\cdot 235\equiv 98\pmod{401}}\\
        \shoveleft{98^{4}\equiv -1\pmod{401}}  \Rightarrow j_{0}=1\\
        \shoveleft{((br)^{2}a^{-1})^{2}\equiv ((268 \cdot  103)^{2} \cdot  235)^{2}\equiv 1\pmod{401} \Rightarrow j_{1}=0}\\
        \shoveleft{(br)^{2}a^{-1}\equiv (268 \cdot  103)^{2} \cdot  235\equiv -1\pmod{401} \Rightarrow j_{2}=1}\\
        \shoveleft{j=j_{0}+2j_{1}+4j_{2}=5 \Rightarrow x\equiv b^{j}r\pmod{401}\equiv 268^{5}\cdot 103\pmod{401}\equiv
        304\pmod{401}}.
    \end{multline*}
\end{example}

\end{document}
