Добавлена седьмая лаба

7 files changed, 264 insertions, 0 deletions

diff --git a/lab7/Cargo.lock b/lab7/Cargo.lock
new file mode 100644
index 0000000..5ccb37a
--- /dev/null
+++ b/lab7/Cargo.lock
@@ -0,0 +1,65 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 3
+
+[[package]]
+name = "az"
+version = "1.2.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "7b7e4c2464d97fe331d41de9d5db0def0a96f4d823b8b32a2efd503578988973"
+
+[[package]]
+name = "gmp-mpfr-sys"
+version = "1.4.10"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "ea3f42dadb6c75f122e9aa87e757ef11d4282f664c9f2e6476a9c2c8970f9d19"
+dependencies = [
+ "libc",
+ "winapi",
+]
+
+[[package]]
+name = "lab7"
+version = "0.1.0"
+dependencies = [
+ "rug",
+]
+
+[[package]]
+name = "libc"
+version = "0.2.134"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "329c933548736bc49fd575ee68c89e8be4d260064184389a5b77517cddd99ffb"
+
+[[package]]
+name = "rug"
+version = "1.17.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "203180f444c95eac53586ed04793ecf6454c5d28f9eca8eead815fc19e136c47"
+dependencies = [
+ "az",
+ "gmp-mpfr-sys",
+ "libc",
+]
+
+[[package]]
+name = "winapi"
+version = "0.3.9"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5c839a674fcd7a98952e593242ea400abe93992746761e38641405d28b00f419"
+dependencies = [
+ "winapi-i686-pc-windows-gnu",
+ "winapi-x86_64-pc-windows-gnu",
+]
+
+[[package]]
+name = "winapi-i686-pc-windows-gnu"
+version = "0.4.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "ac3b87c63620426dd9b991e5ce0329eff545bccbbb34f3be09ff6fb6ab51b7b6"
+
+[[package]]
+name = "winapi-x86_64-pc-windows-gnu"
+version = "0.4.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "712e227841d057c1ee1cd2fb22fa7e5a5461ae8e48fa2ca79ec42cfc1931183f"
diff --git a/lab7/Cargo.toml b/lab7/Cargo.toml
new file mode 100644
index 0000000..c12df81
--- /dev/null
+++ b/lab7/Cargo.toml
@@ -0,0 +1,9 @@
+[package]
+name = "lab7"
+version = "0.1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
+rug = "1.17"
diff --git a/lab7/src/main.rs b/lab7/src/main.rs
new file mode 100644
index 0000000..271116a
--- /dev/null
+++ b/lab7/src/main.rs
@@ -0,0 +1,89 @@
+use rug::{rand::RandState, Complete, Integer};
+use std::io;
+
+fn rabin_miller_test(n: &Integer, k: u32) -> bool {
+    let one = Integer::from(1u32);
+    let two = Integer::from(2u32);
+    let n1 = Integer::from(n - 1u32);
+
+    let mut s = 0;
+    let mut d = n1.clone();
+    while d.mod_u(2u32) == 0 {
+        s += 1u32;
+        d /= 2u32;
+    }
+
+    let mut rand = RandState::new();
+
+    'outer: for _ in 0..k {
+        let bound = n.clone() - 4u32;
+        let a = bound.random_below(&mut rand) + 2u32;
+        let mut x = Integer::from(a.pow_mod_ref(&d, n).unwrap());
+        if x == one || x == n1 {
+            continue;
+        } else {
+            for _ in 0..=s - 1 {
+                x = Integer::from(x.pow_mod_ref(&two, n).unwrap());
+                if x == one {
+                    return false;
+                } else if x == n1 {
+                    continue 'outer;
+                }
+            }
+        }
+        return false;
+    }
+    return true;
+}
+
+fn main() {
+    println!("Введите положительное нечётное число n:");
+    let mut p = String::new();
+    let stdin = io::stdin();
+    match stdin.read_line(&mut p) {
+        Ok(_) => (),
+        Err(_) => {
+            println!("Произошла ошибка при чтении из стандартного ввода");
+            return ();
+        }
+    }
+    let p = match Integer::parse(p) {
+        Ok(parsed) => parsed.complete(),
+        Err(_) => {
+            println!("Не удалось считать число");
+            return ();
+        }
+    };
+    if p.is_divisible(&Integer::from(2u32)) {
+        println!("Введено чётное число");
+        return ();
+    }
+
+    println!("Введите количество раундов k:");
+    let mut k = String::new();
+    match stdin.read_line(&mut k) {
+        Ok(_) => (),
+        Err(_) => {
+            println!("Произошла ошибка при чтении из стандартного ввода");
+            return ();
+        }
+    }
+    let k = match k.trim_end().parse::<u32>() {
+        Ok(parsed) => parsed,
+        Err(_) => {
+            println!("Не удалось считать число");
+            return ();
+        }
+    };
+
+    let is_prime = rabin_miller_test(&p, k);
+    if is_prime {
+        let probability = 1f64 - 0.25f64.powf(k as f64);
+        println!(
+            "Число {} является простым с вероятностью {}",
+            &p, probability
+        );
+    } else {
+        println!("Число не является простым");
+    }
+}
diff --git a/report/lab7/images/test.png b/report/lab7/images/test.png
new file mode 100644
index 0000000..27e48b7
--- /dev/null
+++ b/report/lab7/images/test.png
diff --git a/report/lab7/lab7.pdf b/report/lab7/lab7.pdf
new file mode 100644
index 0000000..99c371c
--- /dev/null
+++ b/report/lab7/lab7.pdf
diff --git a/report/lab7/lab7.tex b/report/lab7/lab7.tex
new file mode 100644
index 0000000..b816976
--- /dev/null
+++ b/report/lab7/lab7.tex
@@ -0,0 +1,66 @@
+\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{{Алгоритмы алгебры и теории чисел}\\{Лабораторная работа №7}}
+\author{Гущин Андрей, 431 группа, 1 подгруппа}
+\date{\the\year{} г.}
+
+\begin{document}
+
+\maketitle
+
+\section{Задача}
+
+Осуществить проверку чисел на простоту с помощью теста Рабина"=Миллера.
+
+\section{Алгоритм}
+
+Тест Миллера --- Рабина опирается на проверку ряда равенств, которые выполняются для
+простых чисел. Если хотя бы одно такое равенство не выполняется, это доказывает
+что число составное.
+
+Пусть $n$ --- простое число и $n - 1 = 2^{s} d$, где $d$ --- нечётно. Тогда для
+любого $a$ из $\mathbb{Z}_n$ выполняется хотя бы одно из условий:
+\begin{enumerate}
+  \item $a^d \equiv 1 \pmod{n}$
+  \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}
+
+\section{Тестирование}
+
+\begin{figure}[H]
+    \centering
+    \includegraphics[width=\textwidth]{test.png}
+\end{figure}
+
+\end{document}
diff --git a/report/lab7/maker.sh b/report/lab7/maker.sh
new file mode 100755
index 0000000..e847acf
--- /dev/null
+++ b/report/lab7/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 <main-doc>.tex -> Запуск процесса, пересобирающего документ при изменениях"
+    echo "./maker.sh doc <main-doc>.tex -> Пересобрать документ"
+    echo "./maker.sh clean -> Удаление сгенерированных файлов"
+    exit 1
+}
+
+case "$1" in
+    watch) watch $2 ;;
+    doc) doc $2 ;;
+    clean) clean ;;
+    *) help ;;
+esac