task.tex

%--------------------seed = 3--------------------
\documentclass{article}
\usepackage[T2A]{fontenc}
\usepackage[cp1251]{inputenc}
\usepackage[russian]{babel}
\usepackage[normalem]{ulem}
\usepackage{mathtools}
\begin{document}
%--------------------Task--------------------
\textbf{\uline{Задание}:} Определить (в контексте теста Миллера--Рабина), являются ли числа:
\begin{flushleft}
\begin{verse}
1) 187;\\
2) 1105,\end{verse}
\end{flushleft}
свидетелями простоты числа 1345.\\
\\
%--------------------Answer--------------------
\textbf{\uline{Ответ}:} Число: 1) является; 2) не является свидетелем простоты.\\
\\
%--------------------Solution--------------------
\textbf{ \uline{Решение}: } Для теста Миллера--Рабина используется следующее утверждение : \\
\noindent\fbox{\parbox{\textwidth}{Пусть $n$ -- простое число и $n-1=2^{s}d$, где $d$ — нечётно.Тогда для любого $a$ из $Z_{n}$ выполняется хотя бы одно из условий:
\begin{verse}
1. $a^{d}\equiv 1{\pmod {n}}$\\
2. Существует целое число $r<s$ такое что$a^{2^{r}d}\equiv -1{\pmod {n}}$\end{verse}}}
\begin{flushright}\footnotesize by Wikipedia \end{flushright}
Тогда $n=1345$, $n-1=1344=2^{s}d$, $s=6$, $d=21$. Переходим к проверке:\\
1) $a=187$;\\
$a^{2^{0}d}\mod n=187^{21}\mod 1345=187\not=1, n-1$;\\
$a^{2^{1}d}\mod n=187^{2}\mod 1345=1344=n-1$;\\
Число является свидетелем простоты.\\
2) $a=1105$;\\
$a^{2^{0}d}\mod n=1105^{21}\mod 1345=415\not=1, n-1$;\\
$a^{2^{1}d}\mod n=415^{2}\mod 1345=65\not=n-1$;\\
$a^{2^{2}d}\mod n=65^{2}\mod 1345=190\not=n-1$;\\
$a^{2^{3}d}\mod n=190^{2}\mod 1345=1130\not=n-1$;\\
$a^{2^{4}d}\mod n=1130^{2}\mod 1345=495\not=n-1$;\\
$a^{2^{5}d}\mod n=495^{2}\mod 1345=235\not=n-1$;\\
Число не является свидетелем простоты.\\
\end{document}