From 0be2be0a92f992bf8ee9eff701cb19658a1e7544 Mon Sep 17 00:00:00 2001 From: Andrew Guschin Date: Thu, 29 Dec 2022 15:20:32 +0400 Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=BB=D0=B5=D0=BD=D1=8B?= =?UTF-8?q?=20=D0=BB=D0=B0=D0=B1=D1=8B=208-15?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- report/lab1/images/test.png | Bin 0 -> 424255 bytes report/lab1/lab1.pdf | Bin 0 -> 450567 bytes report/lab1/lab1.tex | 90 +++++++++++++++++++++++++++++++++++ report/lab1/lab1.xdv | Bin 0 -> 18696 bytes report/lab1/maker.sh | 35 ++++++++++++++ report/lab10/images/test10.png | Bin 0 -> 475309 bytes report/lab10/lab10.pdf | Bin 0 -> 528911 bytes report/lab10/lab10.tex | 81 +++++++++++++++++++++++++++++++ report/lab10/maker.sh | 35 ++++++++++++++ report/lab11/images/test11.png | Bin 0 -> 449004 bytes report/lab11/lab11.pdf | Bin 0 -> 483704 bytes report/lab11/lab11.tex | 80 +++++++++++++++++++++++++++++++ report/lab11/maker.sh | 35 ++++++++++++++ report/lab12/images/test12.png | Bin 0 -> 447170 bytes report/lab12/lab12.pdf | Bin 0 -> 528346 bytes report/lab12/lab12.tex | 89 ++++++++++++++++++++++++++++++++++ report/lab12/maker.sh | 35 ++++++++++++++ report/lab13/images/test13.png | Bin 0 -> 450345 bytes report/lab13/lab13.pdf | Bin 0 -> 501731 bytes report/lab13/lab13.tex | 75 +++++++++++++++++++++++++++++ report/lab13/maker.sh | 35 ++++++++++++++ report/lab15/images/test15.png | Bin 0 -> 473328 bytes report/lab15/lab15.pdf | Bin 0 -> 521002 bytes report/lab15/lab15.tex | 104 ++++++++++++++++++++++++++++++++++++++++ report/lab15/maker.sh | 35 ++++++++++++++ report/lab7/lab7.tex | 5 +- report/lab8/images/test8.png | Bin 0 -> 445326 bytes report/lab8/lab8.pdf | Bin 0 -> 522094 bytes report/lab8/lab8.tex | 105 +++++++++++++++++++++++++++++++++++++++++ report/lab8/maker.sh | 35 ++++++++++++++ report/lab9/images/test9.png | Bin 0 -> 457422 bytes report/lab9/lab9.pdf | Bin 0 -> 517228 bytes report/lab9/lab9.tex | 80 +++++++++++++++++++++++++++++++ report/lab9/maker.sh | 35 ++++++++++++++ 34 files changed, 988 insertions(+), 1 deletion(-) create mode 100644 report/lab1/images/test.png create mode 100644 report/lab1/lab1.pdf create mode 100644 report/lab1/lab1.tex create mode 100644 report/lab1/lab1.xdv create mode 100755 report/lab1/maker.sh create mode 100644 report/lab10/images/test10.png create mode 100644 report/lab10/lab10.pdf create mode 100644 report/lab10/lab10.tex create mode 100755 report/lab10/maker.sh create mode 100644 report/lab11/images/test11.png create mode 100644 report/lab11/lab11.pdf create mode 100644 report/lab11/lab11.tex create mode 100755 report/lab11/maker.sh create mode 100644 report/lab12/images/test12.png create mode 100644 report/lab12/lab12.pdf create mode 100644 report/lab12/lab12.tex create mode 100755 report/lab12/maker.sh create mode 100644 report/lab13/images/test13.png create mode 100644 report/lab13/lab13.pdf create mode 100644 report/lab13/lab13.tex create mode 100755 report/lab13/maker.sh create mode 100644 report/lab15/images/test15.png create mode 100644 report/lab15/lab15.pdf create mode 100644 report/lab15/lab15.tex create mode 100755 report/lab15/maker.sh create mode 100644 report/lab8/images/test8.png create mode 100644 report/lab8/lab8.pdf create mode 100644 report/lab8/lab8.tex create mode 100755 report/lab8/maker.sh create mode 100644 report/lab9/images/test9.png create mode 100644 report/lab9/lab9.pdf create mode 100644 report/lab9/lab9.tex create mode 100755 report/lab9/maker.sh (limited to 'report') diff --git a/report/lab1/images/test.png b/report/lab1/images/test.png new file mode 100644 index 0000000..3425735 Binary files /dev/null and b/report/lab1/images/test.png differ diff --git a/report/lab1/lab1.pdf b/report/lab1/lab1.pdf new file mode 100644 index 0000000..ce1df61 Binary files /dev/null and b/report/lab1/lab1.pdf differ diff --git a/report/lab1/lab1.tex b/report/lab1/lab1.tex new file mode 100644 index 0000000..4b26359 --- /dev/null +++ b/report/lab1/lab1.tex @@ -0,0 +1,90 @@ +\documentclass[a4paper,oneside]{article} + +\usepackage[utf8]{inputenc} +\usepackage[T2A]{fontenc} +\usepackage[english,russian]{babel} + +\usepackage{amsmath} +\usepackage{indentfirst} +\usepackage{mathtools} +\usepackage{amsfonts} +\usepackage{enumitem} +\usepackage{amsthm} +\usepackage{minted} +\setminted{fontsize=\small, breaklines=true, style=emacs, linenos} +\usepackage{graphicx} +\graphicspath{ {./images/} } +\usepackage{float} + +\newtheorem{theorem}{Теорема}[subsection] +\newtheorem*{theorem*}{Теорема} + +% --- Определение --- % +\theoremstyle{definition} +\newtheorem{definition}{Определение}[subsection] +\newtheorem*{definition*}{Определение} +% ------------------- % + +\title{{Алгоритмы алгебры и теории чисел}\\{Лабораторная работа №1}} +\author{Гущин Андрей, 431 группа, 1 подгруппа} +\date{\the\year{} г.} + +\begin{document} + +\maketitle + +\section{Задача} + +Решите сравнение вида $ax \equiv b \pmod{m}$ с помощью алгоритма Евклида. + +\section{Алгоритм} + +Алгоритм Евклида, вычисляющий наибольший общий делитель двух чисел, можно расширить +для нахождения по заданным числам $a$ и $b$ таких целых $x$ и $y$, что +$ax + by = d$, где $d$ --- $\gcd(a, b)$. + +Пусть для положительных целых чисел $a$ и $b$ $(a > b)$ известны $d = \gcd(a, b) += \gcd(b, a \pmod{b})$, а также числа $x'$ и $y'$, для которых $d = x'b + y'(a +\pmod{b})$. Тогда значения $x$ и $y$, являющиеся решениями уравнения $ax + by = +d$, находятся из соотношений +\begin{equation*} + x = y', y = x' - y' \frac{a}{b} +\end{equation*} + +Линейным сравнением называется уравнение вида $ax \equiv b \pmod{m}$. Оно имеет +решение тогда и только тогда, когда $b$ делится на $d = \gcd(a, m)$. Если $d > +1$, то уравнение можно упростить, заменив его на $a'x \equiv b' \pmod{m'}$), +где $a' = a / d$, $b' = b / d$, $m' = m / d$. После такого преобразования числа +$a'$ и $m'$ являются взаимно простыми. + +Алгоритм решения уравнения $a'x \equiv b' \pmod{m'}$) со взаимно простыми $a'$ и +$m'$ состоит из двух частей: +\begin{enumerate} + \item + Решаем уравнение $a'x = 1 \pmod{m'}$). Для этого при помощи расширенного + алгоритма Евклида ищем решение $(x_0, y_0)$ уравнения $a'x + m'y = 1$. Взяв + по модулю $m'$ последнее равенство, получим $a'x_0 = 1 \pmod{m'}$). + \item + Умножим на $b'$ равенство $a'x_0 = 1 \pmod{m'}$). Получим $a'(b'x_0) = b' + \pmod{m'}$), откуда решением исходного уравнения $a'x = b' \pmod{m'}$) будет + $x = b'x_0 \pmod{m'}$). +\end{enumerate} + +Все решения сравнения находят по формуле $x_i = x + m'i$, где $i = 0, \dots, d - +1$. + +\section{Реализация} + +Для реализации программы использовался язык программирования Rust с системой +сборки cargo. + +\inputminted{rust}{../../lab1/src/main.rs} + +\section{Тестирование} + +\begin{figure}[H] + \centering + \includegraphics[width=\textwidth]{test.png} +\end{figure} + +\end{document} diff --git a/report/lab1/lab1.xdv b/report/lab1/lab1.xdv new file mode 100644 index 0000000..9748eb8 Binary files /dev/null and b/report/lab1/lab1.xdv differ diff --git a/report/lab1/maker.sh b/report/lab1/maker.sh new file mode 100755 index 0000000..e847acf --- /dev/null +++ b/report/lab1/maker.sh @@ -0,0 +1,35 @@ +#!/bin/sh + +watch() { + [ -z "$1" ] && echo "Необходимо указать название основного документа" && help + set -o xtrace + latexmk -pdf -f -shell-escape -interaction=nonstopmode -pvc $1 +} + +doc() { + [ -z "$1" ] && echo "Необходимо указать название основного документа" && help + set -o xtrace + latexmk -pdf -f -shell-escape -interaction=nonstopmode $1 +} + +clean() { + set -o xtrace + rm -rf _minted-* + find . -name "*.aux" -exec rm {} \; + rm -f *.dvi *.fdb_latexmk *.fls *.log *.out *.toc +} + +help() { + echo "Использование:" + echo "./maker.sh watch .tex -> Запуск процесса, пересобирающего документ при изменениях" + echo "./maker.sh doc .tex -> Пересобрать документ" + echo "./maker.sh clean -> Удаление сгенерированных файлов" + exit 1 +} + +case "$1" in + watch) watch $2 ;; + doc) doc $2 ;; + clean) clean ;; + *) help ;; +esac diff --git a/report/lab10/images/test10.png b/report/lab10/images/test10.png new file mode 100644 index 0000000..67dfc55 Binary files /dev/null and b/report/lab10/images/test10.png differ diff --git a/report/lab10/lab10.pdf b/report/lab10/lab10.pdf new file mode 100644 index 0000000..50eed16 Binary files /dev/null and b/report/lab10/lab10.pdf differ diff --git a/report/lab10/lab10.tex b/report/lab10/lab10.tex new file mode 100644 index 0000000..2612ecc --- /dev/null +++ b/report/lab10/lab10.tex @@ -0,0 +1,81 @@ +\documentclass[a4paper,oneside]{article} + +\usepackage[utf8]{inputenc} +\usepackage[T2A]{fontenc} +\usepackage[english,russian]{babel} + +\usepackage{amsmath} +\usepackage{mathtools} +\usepackage{amsfonts} +\usepackage{enumitem} +\usepackage{amsthm} +\usepackage{minted} +\setminted{fontsize=\small, breaklines=true, style=emacs, linenos} +\usepackage{graphicx} +\graphicspath{ {./images/} } +\usepackage{float} + +\newtheorem{theorem}{Теорема}[subsection] +\newtheorem*{theorem*}{Теорема} + +% --- Определение --- % +\theoremstyle{definition} +\newtheorem{definition}{Определение}[subsection] +\newtheorem*{definition*}{Определение} +% ------------------- % + +\title{{Алгоритмы алгебры и теории чисел}\\{Лабораторная работа №10}} +\author{Гущин Андрей, 431 группа, 1 подгруппа} +\date{\the\year{} г.} + +\begin{document} + +\maketitle + +\section{Задание} +Осуществить построение большого простого числа с +использованием теоремы Поклингтона. + + +\section{Алгоритм} +Критерий Поклингтона — детерминированный тест на простоту, разработанный +Генри Поклингтоном и Дерриком Генри Лехмером. Критерий Поклингтона +позволяет определять, является ли данное число простым. + +Пусть $n$ — натуральное число. Пусть число $n-1$ имеет простой делитель +$q$, причем ${\displaystyle q>{\sqrt {n}}-1}$. Если найдётся такое целое +число $a$, что выполняются следующие два условия: + +\begin{enumerate} + \item $a^{n-1} \equiv 1 \pmod n$ + \item числа $n$ и $a^{(n-1)/q}-1$ взаимнопросты +\end{enumerate} + +тогда $n$ - простое число. + +Практическая реализация основана на выборе случайного числа в +диапазоне значений от $2^{b - 1} + 1$ до $2^b - 1$ (где $b$ определяет +число бит генерируемого простого числа). Далее это число проверяется на +наличие небольших простых делителей (простые числа меньше 500), и если +таких делителей не найдено, осуществляется проверка с помощью теоремы +Поклингтона. Для этого перед запуском программы вводится значение +верхнего порога $a$, определяющее, что в рамках проверки на простоту с +помощью теоремы Поклингтона будут использоваться целые числа, значение +которых не превосходит $a$. Если число проходит тест, значит оно +является сгенерированным простым числом. Если же число не проходит тест +или у него есть делители среди небольших первых простых чисел, то выбирается +другое число из этого диапазона, пока выбранное число не будет проходить +тест успешно. + + +\section{Реализация} +\inputminted{python}{../../lab10/lab10.py} + + +\section{Тестирование} +\begin{figure}[H] + \centering + \includegraphics[width=0.8\textwidth]{test10.png} +\end{figure} + +\end{document} diff --git a/report/lab10/maker.sh b/report/lab10/maker.sh new file mode 100755 index 0000000..e847acf --- /dev/null +++ b/report/lab10/maker.sh @@ -0,0 +1,35 @@ +#!/bin/sh + +watch() { + [ -z "$1" ] && echo "Необходимо указать название основного документа" && help + set -o xtrace + latexmk -pdf -f -shell-escape -interaction=nonstopmode -pvc $1 +} + +doc() { + [ -z "$1" ] && echo "Необходимо указать название основного документа" && help + set -o xtrace + latexmk -pdf -f -shell-escape -interaction=nonstopmode $1 +} + +clean() { + set -o xtrace + rm -rf _minted-* + find . -name "*.aux" -exec rm {} \; + rm -f *.dvi *.fdb_latexmk *.fls *.log *.out *.toc +} + +help() { + echo "Использование:" + echo "./maker.sh watch .tex -> Запуск процесса, пересобирающего документ при изменениях" + echo "./maker.sh doc .tex -> Пересобрать документ" + echo "./maker.sh clean -> Удаление сгенерированных файлов" + exit 1 +} + +case "$1" in + watch) watch $2 ;; + doc) doc $2 ;; + clean) clean ;; + *) help ;; +esac diff --git a/report/lab11/images/test11.png b/report/lab11/images/test11.png new file mode 100644 index 0000000..ed4a42f Binary files /dev/null and b/report/lab11/images/test11.png differ diff --git a/report/lab11/lab11.pdf b/report/lab11/lab11.pdf new file mode 100644 index 0000000..c4669a0 Binary files /dev/null and b/report/lab11/lab11.pdf differ diff --git a/report/lab11/lab11.tex b/report/lab11/lab11.tex new file mode 100644 index 0000000..9f74180 --- /dev/null +++ b/report/lab11/lab11.tex @@ -0,0 +1,80 @@ +\documentclass[a4paper,oneside]{article} + +\usepackage[utf8]{inputenc} +\usepackage[T2A]{fontenc} +\usepackage[english,russian]{babel} + +\usepackage{amsmath} +\usepackage{mathtools} +\usepackage{amsfonts} +\usepackage{enumitem} +\usepackage{amsthm} +\usepackage{minted} +\setminted{fontsize=\small, breaklines=true, style=emacs, linenos} +\usepackage{graphicx} +\graphicspath{ {./images/} } +\usepackage{float} + +\newtheorem{theorem}{Теорема}[subsection] +\newtheorem*{theorem*}{Теорема} + +% --- Определение --- % +\theoremstyle{definition} +\newtheorem{definition}{Определение}[subsection] +\newtheorem*{definition*}{Определение} +% ------------------- % + +\title{{Алгоритмы алгебры и теории чисел}\\{Лабораторная работа №11}} +\author{Гущин Андрей, 431 группа, 1 подгруппа} +\date{\the\year{} г.} + +\begin{document} + +\maketitle + +\section{Задача} +Реализовать факторизацию Ферма. + +\section{Алгоритм} +Ферма описал свой метод разложения больших чисел на множители. Он +представлял собой первое реальное улучшение по сравнению с +классическим методом попытки найти множитель $n$ путем деления на +все простые числа, не превосходящие $\sqrt{n}$. В основе схемы +факторизации Ферма лежит наблюдение, что поиск множителей нечетного +целого числа $n$ (поскольку степени двойки легко распознаются и +могут быть удалены в самом начале, нет никаких потерь в +предположении, что $n$ нечетно) эквивалентен получению интегральных +решений $x$ и $y$ уравнения $n = x^{2} - y^{2}$. + +Если $n$ --- разность двух квадратов, то очевидно, что $n$ можно разложить на +множители как $n = x^{2}-y^{2} = (x+y)(x-y)$. И наоборот, когда $n$ имеет +разложение $n = ab$, где $a \geq b \geq 1$, тогда мы можем записать $n = +(\frac{a+b}{2})^{2}-(\frac{a-b}{2})^{2}$. + +Более того, поскольку $n$ считается нечетным целым числом, $a$ и $b$ +сами по себе нечетны и, следовательно, $\frac{a+b}{2}$ и +$\frac{a-b}{2}$ будут целыми неотрицательными числами. + +Поиск возможных $x$ и $y$, удовлетворяющих уравнению $n=x^{2}-y^{2}$ или, что то +же самое, уравнению $x^{2}-n=y^{2}$, начинают с определения наименьшее целое +число $k$, для которого $k^{2} \geq n$. Рассмотрим последовательно числа +$k^{2}-n$, $(k+1)^{2}-n$, $(k+2)^{2}-n$, $(k+3)^{2}-n$, $\ldots$, пока не будет +найдено значение $m \geq n$, делающее $m^{2}-n$ квадратом. Процесс не может +продолжаться бесконечно, потому что в конце концов мы придем к $ +(\frac{n+1}{2})^{2} - n = (\frac{n-1}{2})^{2}$ представлению $n$, +соответствующее тривиальной факторизации $n=n.1$. Если эта точка достигается без +обнаружения разности квадратов ранее, то $n$ не имеет других делителей, кроме +$n$ и $1$, и в этом случае оно является простым числом. + + +\section{Реализация} +\inputminted{python}{../../lab11/lab11.py} + + +\section{Тестирование} +\begin{figure}[H] + \centering + \includegraphics[width=0.8\textwidth]{test11.png} +\end{figure} + +\end{document} diff --git a/report/lab11/maker.sh b/report/lab11/maker.sh new file mode 100755 index 0000000..e847acf --- /dev/null +++ b/report/lab11/maker.sh @@ -0,0 +1,35 @@ +#!/bin/sh + +watch() { + [ -z "$1" ] && echo "Необходимо указать название основного документа" && help + set -o xtrace + latexmk -pdf -f -shell-escape -interaction=nonstopmode -pvc $1 +} + +doc() { + [ -z "$1" ] && echo "Необходимо указать название основного документа" && help + set -o xtrace + latexmk -pdf -f -shell-escape -interaction=nonstopmode $1 +} + +clean() { + set -o xtrace + rm -rf _minted-* + find . -name "*.aux" -exec rm {} \; + rm -f *.dvi *.fdb_latexmk *.fls *.log *.out *.toc +} + +help() { + echo "Использование:" + echo "./maker.sh watch .tex -> Запуск процесса, пересобирающего документ при изменениях" + echo "./maker.sh doc .tex -> Пересобрать документ" + echo "./maker.sh clean -> Удаление сгенерированных файлов" + exit 1 +} + +case "$1" in + watch) watch $2 ;; + doc) doc $2 ;; + clean) clean ;; + *) help ;; +esac diff --git a/report/lab12/images/test12.png b/report/lab12/images/test12.png new file mode 100644 index 0000000..6004670 Binary files /dev/null and b/report/lab12/images/test12.png differ diff --git a/report/lab12/lab12.pdf b/report/lab12/lab12.pdf new file mode 100644 index 0000000..baefde4 Binary files /dev/null and b/report/lab12/lab12.pdf differ diff --git a/report/lab12/lab12.tex b/report/lab12/lab12.tex new file mode 100644 index 0000000..8077040 --- /dev/null +++ b/report/lab12/lab12.tex @@ -0,0 +1,89 @@ +\documentclass[a4paper,oneside]{article} + +\usepackage[utf8]{inputenc} +\usepackage[T2A]{fontenc} +\usepackage[english,russian]{babel} + +\usepackage{amsmath} +\usepackage{mathtools} +\usepackage{amsfonts} +\usepackage{enumitem} +\usepackage{amsthm} +\usepackage{minted} +\setminted{fontsize=\small, breaklines=true, style=emacs, linenos} +\usepackage{graphicx} +\graphicspath{ {./images/} } +\usepackage{float} + +\newtheorem{theorem}{Теорема}[subsection] +\newtheorem*{theorem*}{Теорема} + +% --- Определение --- % +\theoremstyle{definition} +\newtheorem{definition}{Определение}[subsection] +\newtheorem*{definition*}{Определение} +% ------------------- % + +\title{{Алгоритмы алгебры и теории чисел}\\{Лабораторная работа №12}} +\author{Гущин Андрей, 431 группа, 1 подгруппа} +\date{\the\year{} г.} + +\begin{document} + +\maketitle + +\section{Задача} +Осуществить факторизацию с помощью алгоритма Диксона. + + +\section{Алгоритм} +Алгоритм Диксона — алгоритм факторизации, использующий +в своей основе идею Лежандра, заключающуюся в поиске пары целых чисел +$x$ и $y$ таких, что $x^2 \equiv y^2\pmod{n}$ и $x \not\equiv \pm +y\pmod{n}$. Он является обобщением метода Ферма. + +В общем виде алгоритм можно представить следующим образом: +\begin{enumerate} + \item + Составить факторную базу ${\displaystyle \mathrm {B} + =\left\{{p_{1},p_{2},\dots ,p_{h}}\right\}}$, состоящую из всех + простых чисел ${\displaystyle p \leq M = L\left({n}\right)^{\frac + {1}{2}}}$, где ${\displaystyle L\left({n}\right)=\exp {\left({\sqrt + {\ln {n}\cdot \ln {\ln {n}}}}\right)}}$. + \item Выбрать такое случайное $b$, что $\sqrt{n}.tex -> Запуск процесса, пересобирающего документ при изменениях" + echo "./maker.sh doc .tex -> Пересобрать документ" + echo "./maker.sh clean -> Удаление сгенерированных файлов" + exit 1 +} + +case "$1" in + watch) watch $2 ;; + doc) doc $2 ;; + clean) clean ;; + *) help ;; +esac diff --git a/report/lab13/images/test13.png b/report/lab13/images/test13.png new file mode 100644 index 0000000..97c5351 Binary files /dev/null and b/report/lab13/images/test13.png differ diff --git a/report/lab13/lab13.pdf b/report/lab13/lab13.pdf new file mode 100644 index 0000000..db6cbfa Binary files /dev/null and b/report/lab13/lab13.pdf differ diff --git a/report/lab13/lab13.tex b/report/lab13/lab13.tex new file mode 100644 index 0000000..61101c7 --- /dev/null +++ b/report/lab13/lab13.tex @@ -0,0 +1,75 @@ +\documentclass[a4paper,oneside]{article} + +\usepackage[utf8]{inputenc} +\usepackage[T2A]{fontenc} +\usepackage[english,russian]{babel} + +\usepackage{amsmath} +\usepackage{mathtools} +\usepackage{amsfonts} +\usepackage{enumitem} +\usepackage{amsthm} +\usepackage{minted} +\setminted{fontsize=\small, breaklines=true, style=emacs, linenos} +\usepackage{graphicx} +\graphicspath{ {./images/} } +\usepackage{float} + +\newtheorem{theorem}{Теорема}[subsection] +\newtheorem*{theorem*}{Теорема} + +% --- Определение --- % +\theoremstyle{definition} +\newtheorem{definition}{Определение}[subsection] +\newtheorem*{definition*}{Определение} +% ------------------- % + +\title{{Алгоритмы алгебры и теории чисел}\\{Лабораторная работа №13}} +\author{Гущин Андрей, 431 группа, 1 подгруппа} +\date{\the\year{} г.} + +\begin{document} + +\maketitle + +\section{Задача} + +Реализация алгоритма полиномиального деления (PDF). + + +\section{Алгоритм} + +На вход алгоритма подаются многочлены $p_1(x) = \sum_0^m c_i x^i$ и $p_2(x) = +\sum_0^n d_i x^i$ над полем $m \geq n \geq 0$ и $d_n \neq 0$. Этот алгоритм +будет работать и над областью целостности $J$ при условии, что $d_n$ обратим в +$J$. + +В результате получаем частное $q(x) = \sum_0^{m - n} q_i x^i$ и остаток $r(x) = +\sum_0^{n - 1} r_i x^i$, обладающие свойством евклидовости. + +В общем виде алгоритм можно представить следующим образом: +\begin{enumerate} + \item + Основной цикл: для $k$ от $m - n$ до $0$ выполнять $q_k = c_{n + k} + \cdot d_n^{-1}$, для $j$ от $n + k - 1$ до $k$ выполнять $c_j = c_j - + q_k \cdot d_{j - k}$. + \item + Выход: вернуть $q_i$, где $i = 0, 1, \dots, m - n$, и коэффициенты + полинома $q(x)$, вычисленного на шаге $1$, и $r_j$, где $i = 0, 1, + \dots, n - 1$, коэффициенты полинома $r(x)$, где $r_j = c_j$ (где $c_j$ + также вычислены на шаге $1$). +\end{enumerate} + + +\section{Реализация} +\inputminted{python}{../../lab13/lab13.py} + + +\section{Тестирование} +\begin{figure}[H] + \centering + \includegraphics[width=0.8\textwidth]{test13.png} +\end{figure} + + +\end{document} diff --git a/report/lab13/maker.sh b/report/lab13/maker.sh new file mode 100755 index 0000000..e847acf --- /dev/null +++ b/report/lab13/maker.sh @@ -0,0 +1,35 @@ +#!/bin/sh + +watch() { + [ -z "$1" ] && echo "Необходимо указать название основного документа" && help + set -o xtrace + latexmk -pdf -f -shell-escape -interaction=nonstopmode -pvc $1 +} + +doc() { + [ -z "$1" ] && echo "Необходимо указать название основного документа" && help + set -o xtrace + latexmk -pdf -f -shell-escape -interaction=nonstopmode $1 +} + +clean() { + set -o xtrace + rm -rf _minted-* + find . -name "*.aux" -exec rm {} \; + rm -f *.dvi *.fdb_latexmk *.fls *.log *.out *.toc +} + +help() { + echo "Использование:" + echo "./maker.sh watch .tex -> Запуск процесса, пересобирающего документ при изменениях" + echo "./maker.sh doc .tex -> Пересобрать документ" + echo "./maker.sh clean -> Удаление сгенерированных файлов" + exit 1 +} + +case "$1" in + watch) watch $2 ;; + doc) doc $2 ;; + clean) clean ;; + *) help ;; +esac diff --git a/report/lab15/images/test15.png b/report/lab15/images/test15.png new file mode 100644 index 0000000..a607878 Binary files /dev/null and b/report/lab15/images/test15.png differ diff --git a/report/lab15/lab15.pdf b/report/lab15/lab15.pdf new file mode 100644 index 0000000..dd9c74e Binary files /dev/null and b/report/lab15/lab15.pdf differ diff --git a/report/lab15/lab15.tex b/report/lab15/lab15.tex new file mode 100644 index 0000000..077ba29 --- /dev/null +++ b/report/lab15/lab15.tex @@ -0,0 +1,104 @@ +\documentclass[a4paper,oneside]{article} + +\usepackage[utf8]{inputenc} +\usepackage[T2A]{fontenc} +\usepackage[english,russian]{babel} + +\usepackage{amsmath} +\usepackage{mathtools} +\usepackage{amsfonts} +\usepackage{enumitem} +\usepackage{amsthm} +\usepackage{minted} +\setminted{fontsize=\small, breaklines=true, style=emacs, linenos} +\usepackage{graphicx} +\graphicspath{ {./images/} } +\usepackage{float} + +\newtheorem{theorem}{Теорема}[subsection] +\newtheorem*{theorem*}{Теорема} + +% --- Определение --- % +\theoremstyle{definition} +\newtheorem{definition}{Определение}[subsection] +\newtheorem*{definition*}{Определение} +% ------------------- % + +\title{{Алгоритмы алгебры и теории чисел}\\{Лабораторная работа №15}} +\author{Гущин Андрей, 431 группа, 1 подгруппа} +\date{\the\year{} г.} + +\begin{document} + +\maketitle + +\section{Задача} + +Вычисление значений и корней полиномов + + +\section{Алгоритм} + + +\subsection{Значение многочлена} + +При вычислении значений многочленов очень широкое применение получило правило +Горнера. Метод назван в честь британского математика Уильяма Джорджа Горнера. + +В соответствии с этим правилом многочлен $n$-й степени: +\begin{equation*} + P_n(x)=a_0 x^n + a_1 x^{n-1} + \dots + a_{n-1} x + a_n +\end{equation*} +представляется в виде +\begin{equation*} + P_n(x) =(\dots((a_0 x + a_1) x + a_2) x + \dots + a_{n-1}) x + a_n +\end{equation*} + +Вычисление значения многочлена производится в порядке, определяемом скобками. + +\subsection{Корни многочлена} + +Схема Горнера - способ деления многочлена +$$P_n(x) = \sum_{i=0}^{n} a_i x^{n - i} = a_0 x^n + a_1 x^{n - 1} + \cdots + +a_n$$ на бином $x - a$. Работать придётся с таблицей, первая строка которой +содержит коэффициенты заданного многочлена. Первым элементом второй строки +будет число $a$, взятое из бинома $x - a$. + +Вторая строка таблицы заполняется постепенно. Второй элемент этой строки +(обозначим его $b_0$) равен $a_0$, т.е., по сути, мы просто переносим вниз число +$a_0$. + +Следующий элемент второй строки, который мы обозначим как $b_1$, получается по +такой формуле: $b_1 = a \cdot b_0 + a_1$. Далее находим элемент $b_2$ по +формуле $b_2 = a \cdot b_1 + a_2$ и т.д. + +В конечном итоге, мы вычислим последний элемент $b_n = a \cdot b_{n - 1} + a_n$. + +После деления исходного многочлена $n$-й степени $P_n(x)$ на бином $x - a$, +получим многочлен, степень которого на единицу меньше исходного, т.е. равна $n - +1$. + +Последнее число второй строки, т.е. $b_n$, есть остаток от деления $P_n ( x )$ +на $x - a$: +\begin{equation*} + \sum_{i=0}^{n} a_i x^{n - i} = a_0 x^n + a_1 x^{n - 1} + \dots + a_n = (x - a) \cdot (b_0 x^{n - 1} + b_1 x^{n - 2} + \dots + b_{n - 1}) + b_n +\end{equation*} + +Таким образом, по теореме Безу это означает, что число $b_n$ равно значению +многочлена $P_n ( x )$ при $x = a$, т.е. $b_n = P_n ( a )$. + +Если $b_n = 0$, то исходный многочлен делится на бином $x - a$ нацело, т.е. +число $a$ является корнем этого многочлена. + + +\section{Реализация} +\inputminted{python}{../../lab15/lab15.py} + + +\section{Тестирование} +\begin{figure}[H] + \centering + \includegraphics[width=0.8\textwidth]{test15.png} +\end{figure} + +\end{document} diff --git a/report/lab15/maker.sh b/report/lab15/maker.sh new file mode 100755 index 0000000..e847acf --- /dev/null +++ b/report/lab15/maker.sh @@ -0,0 +1,35 @@ +#!/bin/sh + +watch() { + [ -z "$1" ] && echo "Необходимо указать название основного документа" && help + set -o xtrace + latexmk -pdf -f -shell-escape -interaction=nonstopmode -pvc $1 +} + +doc() { + [ -z "$1" ] && echo "Необходимо указать название основного документа" && help + set -o xtrace + latexmk -pdf -f -shell-escape -interaction=nonstopmode $1 +} + +clean() { + set -o xtrace + rm -rf _minted-* + find . -name "*.aux" -exec rm {} \; + rm -f *.dvi *.fdb_latexmk *.fls *.log *.out *.toc +} + +help() { + echo "Использование:" + echo "./maker.sh watch .tex -> Запуск процесса, пересобирающего документ при изменениях" + echo "./maker.sh doc .tex -> Пересобрать документ" + echo "./maker.sh clean -> Удаление сгенерированных файлов" + exit 1 +} + +case "$1" in + watch) watch $2 ;; + doc) doc $2 ;; + clean) clean ;; + *) help ;; +esac diff --git a/report/lab7/lab7.tex b/report/lab7/lab7.tex index b816976..6ce3ee7 100644 --- a/report/lab7/lab7.tex +++ b/report/lab7/lab7.tex @@ -36,6 +36,7 @@ Осуществить проверку чисел на простоту с помощью теста Рабина"=Миллера. + \section{Алгоритм} Тест Миллера --- Рабина опирается на проверку ряда равенств, которые выполняются для @@ -49,12 +50,14 @@ \item Существует целое число $r < s$ такое что $a^{2^r d} \equiv -1 \pmod{n}$ \end{enumerate} + \section{Реализация} Для реализации программы использовался язык программирования Rust с системой сборки cargo. Для работы с длинной арифметикой использовалась библиотека rug. -\inputminted[fontsize=\small, breaklines=true, style=emacs, linenos]{rust}{../../lab7/src/main.rs} +\inputminted{rust}{../../lab7/src/main.rs} + \section{Тестирование} diff --git a/report/lab8/images/test8.png b/report/lab8/images/test8.png new file mode 100644 index 0000000..362ab76 Binary files /dev/null and b/report/lab8/images/test8.png differ diff --git a/report/lab8/lab8.pdf b/report/lab8/lab8.pdf new file mode 100644 index 0000000..0ce50b0 Binary files /dev/null and b/report/lab8/lab8.pdf differ diff --git a/report/lab8/lab8.tex b/report/lab8/lab8.tex new file mode 100644 index 0000000..8ba3421 --- /dev/null +++ b/report/lab8/lab8.tex @@ -0,0 +1,105 @@ +\documentclass[a4paper,oneside]{article} + +\usepackage[utf8]{inputenc} +\usepackage[T2A]{fontenc} +\usepackage[english,russian]{babel} + +\usepackage{amsmath} +\usepackage{mathtools} +\usepackage{amsfonts} +\usepackage{enumitem} +\usepackage{amsthm} +\usepackage{minted} +\setminted{fontsize=\small, breaklines=true, style=emacs, linenos} +\usepackage{graphicx} +\graphicspath{ {./images/} } +\usepackage{float} + +\newtheorem{theorem}{Теорема}[subsection] +\newtheorem*{theorem*}{Теорема} + +% --- Определение --- % +\theoremstyle{definition} +\newtheorem{definition}{Определение}[subsection] +\newtheorem*{definition*}{Определение} +% ------------------- % + +\title{{Алгоритмы алгебры и теории чисел}\\{Лабораторная работа №8}} +\author{Гущин Андрей, 431 группа, 1 подгруппа} +\date{\the\year{} г.} + +\begin{document} + + +\maketitle + +\section{Задача} + + Осуществить проверку чисел на простоту с помощью + полиномиального теста распознавания простоты. + +\section{Алгоритм} + + Тест Агравала — Каяла — Саксены (тест AKS) — единственный известный на + данный момент универсальный (то есть применимый ко всем числам) + полиномиальный, детерминированный и безусловный (то есть не зависящий от + недоказанных гипотез) тест простоты чисел, основанный на обобщении малой + теоремы Ферма на многочлены. + + + Если существует ${\displaystyle r\in \mathbb {Z}}$ такое, что + ${\displaystyle o_{r}(n)>\log ^{2}n}$ и для любого ${\displaystyle a}$ + от 1 до ${\displaystyle \left\lfloor {\sqrt {\varphi (r) }} \log(n) + \right \rfloor }$ выполняется сравнение ${\displaystyle (x+a)^{n}\equiv + (x^{n}+a){\pmod {x^{r}-1,\;n}}}$, то ${\displaystyle n}$ — либо простое + число, либо степень простого числа. + + Здесь и далее ${\displaystyle o_{r}(n)}$ обозначает показатель числа + ${\displaystyle n}$ по модулю ${\displaystyle r}$, $\log$ — двоичный + логарифм и $\varphi (\cdot )$ — функция Эйлера. + + Сравнение по двум модулям вида \[{\displaystyle a(x)\equiv b(x){\pmod + {h(x),\;n}}}\] для многочленов ${\displaystyle a(x),\;b(x)\in \mathbb + {Z} [x]}$ означает, что существует ${\displaystyle g(x)\in \mathbb {Z} + [x]}$ такой, что все коэффициенты многочлена ${\displaystyle a(x) - b(x) + - g(x)h(x)}$ кратны $n$, где $\mathbb {Z} [x]$ — кольцо многочленов от + $x$ над целыми числами. + + \textbf{Показателем}, или \textbf{мультипликативным порядком}, целого + числа $a$ по модулю $m$ называется наименьшее положительное целое число + $\ell$, такое, что ${\displaystyle a^{\ell }\equiv 1{\pmod {m}}.}$ + + + В общем виде алгоритм можно представить следующим образом: + + \begin{enumerate} + \item Подается на проверку число $n$. + \item Проверить, является ли $n$ степенью числа: если $n = a^b$ для + целых чисел $a > 1$, $b > 1$. Если да, вернуть ''составное''. + \item Найти такое наименьшее $r$ (взаимнопростое с $n$), что + $o_{r}(n) > (log_2 \; n)^2$. + \item Если $1 < $НОД$(a,\;n) < n$ для некоторого $a \leq r$, + вернуть ''составное''. + \item Если $n\leq r$, вернуть ''простое''. + \item Если для всех $a$ от $1$ до $\left\lfloor {\sqrt {\varphi + (r)}}\log(n)\right\rfloor$ верно, что $(x+a)^{n}\equiv x^{n}+a{\pmod + {x^{r}-1,\;n}}$, вернуть ''простое''. + \item Иначе вернуть ''составное''. + \end{enumerate} + + Для вычисления коэффициентов многочлена, полученного из $(x+a)^{n}\equiv + x^{n}+a{\pmod {x^{r}-1,\;n}}$, с целью проверки их делимости на + исследуемое число $n$ использовался треугольник Паскаля. + + +\section{Реализация} +\inputminted{python}{../../lab8/lab8.py} + +\section{Тестирование} + +\begin{figure}[H] + \centering + \includegraphics[width=0.8\textwidth]{test8.png} +\end{figure} + +\end{document} diff --git a/report/lab8/maker.sh b/report/lab8/maker.sh new file mode 100755 index 0000000..e847acf --- /dev/null +++ b/report/lab8/maker.sh @@ -0,0 +1,35 @@ +#!/bin/sh + +watch() { + [ -z "$1" ] && echo "Необходимо указать название основного документа" && help + set -o xtrace + latexmk -pdf -f -shell-escape -interaction=nonstopmode -pvc $1 +} + +doc() { + [ -z "$1" ] && echo "Необходимо указать название основного документа" && help + set -o xtrace + latexmk -pdf -f -shell-escape -interaction=nonstopmode $1 +} + +clean() { + set -o xtrace + rm -rf _minted-* + find . -name "*.aux" -exec rm {} \; + rm -f *.dvi *.fdb_latexmk *.fls *.log *.out *.toc +} + +help() { + echo "Использование:" + echo "./maker.sh watch .tex -> Запуск процесса, пересобирающего документ при изменениях" + echo "./maker.sh doc .tex -> Пересобрать документ" + echo "./maker.sh clean -> Удаление сгенерированных файлов" + exit 1 +} + +case "$1" in + watch) watch $2 ;; + doc) doc $2 ;; + clean) clean ;; + *) help ;; +esac diff --git a/report/lab9/images/test9.png b/report/lab9/images/test9.png new file mode 100644 index 0000000..d6bc2e8 Binary files /dev/null and b/report/lab9/images/test9.png differ diff --git a/report/lab9/lab9.pdf b/report/lab9/lab9.pdf new file mode 100644 index 0000000..ef0efcc Binary files /dev/null and b/report/lab9/lab9.pdf differ diff --git a/report/lab9/lab9.tex b/report/lab9/lab9.tex new file mode 100644 index 0000000..b47474a --- /dev/null +++ b/report/lab9/lab9.tex @@ -0,0 +1,80 @@ +\documentclass[a4paper,oneside]{article} + +\usepackage[utf8]{inputenc} +\usepackage[T2A]{fontenc} +\usepackage[english,russian]{babel} + +\usepackage{amsmath} +\usepackage{mathtools} +\usepackage{amsfonts} +\usepackage{enumitem} +\usepackage{amsthm} +\usepackage{minted} +\setminted{fontsize=\small, breaklines=true, style=emacs, linenos} +\usepackage{graphicx} +\graphicspath{ {./images/} } +\usepackage{float} + +\newtheorem{theorem}{Теорема}[subsection] +\newtheorem*{theorem*}{Теорема} + +% --- Определение --- % +\theoremstyle{definition} +\newtheorem{definition}{Определение}[subsection] +\newtheorem*{definition*}{Определение} +% ------------------- % + +\title{{Алгоритмы алгебры и теории чисел}\\{Лабораторная работа №9}} +\author{Гущин Андрей, 431 группа, 1 подгруппа} +\date{\the\year{} г.} + +\begin{document} + +\maketitle + +\section{Задача} + +Осуществить построение большого простого числа с +использованием критерия Люка. + + +\section{Алгоритм} + +В теории чисел тест простоты Люка — это тест простоты натурального числа +n; для его работы необходимо знать разложение $n-1$ на множители. Для +простого числа n простые множители числа $n-1$ вместе с некоторым +основанием a составляют сертификат Пратта, который позволяет подтвердить +за полиномиальное время, что число n является простым. + +Пусть n > 1 — натуральное число. Если существует целое $a$ такое, что +${\displaystyle 1.tex -> Запуск процесса, пересобирающего документ при изменениях" + echo "./maker.sh doc .tex -> Пересобрать документ" + echo "./maker.sh clean -> Удаление сгенерированных файлов" + exit 1 +} + +case "$1" in + watch) watch $2 ;; + doc) doc $2 ;; + clean) clean ;; + *) help ;; +esac -- cgit v1.2.3