Добавлены лабы 8-15HEADmaster

46 files changed, 1631 insertions, 66 deletions

diff --git a/.gitignore b/.gitignore
index 5a938cf..b48e842 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,5 +1,6 @@
 .*
 lab*/target
+venv
 
 *.dvi
 *.aux
diff --git a/lab1/Cargo.lock b/lab1/Cargo.lock
index 1281335..006d67e 100644
--- a/lab1/Cargo.lock
+++ b/lab1/Cargo.lock
@@ -3,63 +3,5 @@
 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 = "lab1"
 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/lab1/Cargo.toml b/lab1/Cargo.toml
index 1370852..b71c28d 100644
--- a/lab1/Cargo.toml
+++ b/lab1/Cargo.toml
@@ -6,4 +6,3 @@ 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/lab1/src/main.rs b/lab1/src/main.rs
index e7a11a9..bae0284 100644
--- a/lab1/src/main.rs
+++ b/lab1/src/main.rs
@@ -1,3 +1,59 @@
-fn main() {
-    println!("Hello, world!");
+use std::io;
+use std::io::Write;
+
+fn egcd(a: i64, b: i64) -> (i64, i64, i64) {
+    if a == 0 {
+        return (b, 0, 1);
+    }
+    let p = egcd(b % a, a);
+    let d = p.0;
+    let x1 = p.1;
+    let y1 = p.2;
+    let x = y1 - (b / a) * x1;
+    let y = x1;
+    return (d, x, y);
+}
+
+fn main() -> io::Result<()> {
+    let stdin = io::stdin();
+
+    print!("Введите модуль m: ");
+    io::stdout().flush().unwrap();
+    let mut m = String::new();
+    stdin.read_line(&mut m)?;
+    let mut m = m.trim_end().parse::<i64>().unwrap();
+
+    print!("Введите a: ");
+    io::stdout().flush().unwrap();
+    let mut a = String::new();
+    stdin.read_line(&mut a)?;
+    let mut a = a.trim_end().parse::<i64>().unwrap() % m;
+
+    print!("Введите b: ");
+    io::stdout().flush().unwrap();
+    let mut b = String::new();
+    stdin.read_line(&mut b)?;
+    let mut b = b.trim_end().parse::<i64>().unwrap() % m;
+
+    let (d, _, _) = egcd(a, m);
+    if b % d != 0 {
+        println!("Сравнение не имеет решений");
+    } else {
+        println!("Сравнение имеет {d} решений");
+        a /= d;
+        b /= d;
+        m /= d;
+
+        let (_, x, _) = egcd(a, m);
+        let mut x0 = (x * b) % m;
+        if x0 < 0 {
+            x0 = m + x0;
+        }
+        for i in 0..d {
+            print!("{} ", x0 + m * i);
+        }
+        println!("");
+    }
+
+    return Ok(());
 }
diff --git a/lab10/lab10.py b/lab10/lab10.py
new file mode 100644
index 0000000..2e63379
--- /dev/null
+++ b/lab10/lab10.py
@@ -0,0 +1,96 @@
+import math

+import random

+

+

+def erathosphene(n):

+    is_prime = [True] * n

+    p = 2

+    while p * p < n:

+        cur = p * p;

+        while cur < n:

+            is_prime[cur] = False;

+            cur += p;

+        while not is_prime[p + 1]:

+            p += 1;

+        p += 1

+    primes = []

+    for i, p in enumerate(is_prime):

+        if p:

+            primes.append(i)

+    return primes[2:]

+

+

+def fast_power(base, power):

+    result = 1

+    while power > 0:

+        if power % 2 == 0:

+            power = power // 2

+            base *= base

+        else:

+            power -= 1

+            result = result * base

+            power = power // 2

+            base *= base

+    return result

+

+

+def get_only_prime_divisors(n):

+    factors = []

+    if (n % 2 == 0):

+        factors.append(2)

+

+    while (n % 2 == 0):

+        n = n // 2

+

+    for i in range(3, int(math.sqrt(n)) + 1, 2):

+        if (n % i == 0):

+            factors.append(i)

+

+        while (n % i == 0):

+            n = n // i

+

+    if (n > 2):

+        factors.append(n)

+

+    return factors

+

+

+def pocklington_criterion(n, borded_a):

+    prev_n = n - 1

+    prime_divisors = get_only_prime_divisors(prev_n)

+    prime_divisors = filter(lambda q: q > math.sqrt(n) - 1, prime_divisors)

+

+    for a in range(2, borded_a):

+        if pow(a, prev_n, n) != 1:

+            continue

+        for q in prime_divisors:

+            if math.gcd(n, fast_power(a, prev_n // q) - 1) == 1:

+                return True

+    return False

+

+

+def get_random_number(n):

+    while True:

+        number = random.randrange(2 ** (n-1) + 1, 2 ** n - 1)

+        for divisor in first_primes_list:

+            if number % divisor == 0 and divisor ** 2 <= number:

+                break

+        else:

+            return number

+

+

+def create_prime(n, a):

+    while True:

+        number = get_random_number(n)

+        if pocklington_criterion(number, a):

+            return number

+

+

+first_primes_list = erathosphene(500)

+if __name__ == "__main__":

+    print("Введите количество бит генерируемого простого числа:")

+    n = int(input())

+    print("Введите верхнюю границу числа 'a' в критерии Поклингтона (не меньше 3):")

+    a = int(input())

+    result = create_prime(n, a)

+    print(f"Сгенерированное простое число: {result}")

diff --git a/lab11/lab11.py b/lab11/lab11.py
new file mode 100644
index 0000000..c369645
--- /dev/null
+++ b/lab11/lab11.py
@@ -0,0 +1,26 @@
+import math

+

+

+def fermat_factorization(n):

+    start_x = math.ceil(math.sqrt(n))

+    cur_x = start_x

+    squared_y = 0

+    for x in range(start_x, (n + 1) // 2):

+        cur_x = x

+        squared_y = math.sqrt(x ** 2 - n)

+        if math.isclose(int(squared_y), squared_y, rel_tol=1e-20):

+            break

+

+    multiplier_p = cur_x + squared_y

+    multiplier_q = cur_x - squared_y

+    if multiplier_p == n // multiplier_q:

+        factors = [int(multiplier_p), int(multiplier_q)]

+        print(f"Простые множители для {n}: {factors}")

+    else:

+        print(f"Метод Ферма не нашел подходящую пару множителей для {n}")

+

+

+if __name__ == "__main__":

+    print("Введите нечётное целое число n:")

+    n = int(input())

+    fermat_factorization(n)

diff --git a/lab12/lab12.py b/lab12/lab12.py
new file mode 100644
index 0000000..5a7eae9
--- /dev/null
+++ b/lab12/lab12.py
@@ -0,0 +1,77 @@
+from math import gcd, sqrt, log, exp

+

+

+def get_only_prime_divisors(n):

+    factors = []

+    if (n % 2 == 0):

+        factors.append(2)

+

+    while (n % 2 == 0):

+        n = n // 2

+

+    for i in range(3, int(sqrt(n)) + 1, 2):

+        if (n % i == 0):

+            factors.append(i)

+

+        while (n % i == 0):

+            n = n // i

+

+    if (n > 2):

+        factors.append(n)

+

+    return factors

+

+

+def erathosphene(n):

+    is_prime = [True] * n

+    p = 2

+    while p * p < n:

+        cur = p * p;

+        while cur < n:

+            is_prime[cur] = False;

+            cur += p;

+        while not is_prime[p + 1]:

+            p += 1;

+        p += 1

+    primes = []

+    for i, p in enumerate(is_prime):

+        if p:

+            primes.append(i)

+    return primes[2:]

+

+

+def get_factor_base(n):

+    m = sqrt(exp(sqrt(log(n) * log(log(n)))))

+    factor_base = erathosphene(int(m))

+    return factor_base

+

+

+def dixon_factorization(n):

+    factor_base = get_factor_base(n)

+    print("Фактор база: ", factor_base)

+    smooth_b = []

+    for b in range(int(sqrt(n)), n):

+        a = b ** 2 % n

+        for fact in factor_base:

+            f = fact ** 2 % n

+            if a == f:

+                smooth_b.append((b, fact))

+

+    factors = []

+    for a, fact in smooth_b:

+        factor = gcd(a - fact, n)

+        if factor != 1:

+            factors.append(factor)

+

+    return list(set(factors))

+

+

+def main():

+    print("Введите нечётное целое число n:")

+    n = int(input())

+    factors = dixon_factorization(n)

+    print(f"Простые множители {n}:", factors)

+

+

+if __name__ == "__main__":

+    main()

diff --git a/lab13/lab13.py b/lab13/lab13.py
new file mode 100644
index 0000000..993ad81
--- /dev/null
+++ b/lab13/lab13.py
@@ -0,0 +1,77 @@
+def poly_print(f):

+    n, f_c = f

+    n = len(f_c) - 1

+    poly_str = ""

+    for i in range(len(f_c)):

+        cur_cf = f_c[i]

+        if not cur_cf:

+            continue

+        if cur_cf > 0:

+            sign = "+"

+        else:

+            cur_cf = -cur_cf

+            sign = "-"

+        poly_str += f"{sign} {cur_cf}x^{n - i} "

+    poly_str = poly_str[:len(poly_str) - 4]

+    if poly_str[0] == "+":

+        poly_str = poly_str[2:]

+    return poly_str

+

+

+def poly_reduction(f):

+    n, f_c = f

+    i = 0

+    while i < len(f_c) and f_c[i] == 0:

+        n -= 1

+        i += 1

+    return n, f_c[i:]

+

+

+def inverse(n, field):

+    x = 0

+    for _ in range(field):

+        if (n * x) % field != 1:

+            x += 1

+        else:

+            break

+    return x

+

+

+def pdf(f, g, field):

+    m, f_c = f

+    n, g_c = g

+    f_c.reverse()

+    g_c.reverse()

+

+    q_c = [0] * (m + 1)

+    r_c = f_c

+

+    for k in range(m - n, -1, -1):

+        q_c[k] = (f_c[n + k] * inverse(g_c[n], field)) % field

+        for j in range(n + k - 1, k - 1, -1):

+            r_c[j] = (r_c[j] - q_c[k] * g_c[j - k]) % field

+

+    q_c.reverse()

+    r_c.reverse()

+

+    return (m, q_c), (n, r_c)

+

+

+if __name__ == "__main__":

+    print("Введите коэффициенты первого многочлена:")

+    cf = list(map(int, input().split()))

+    f = poly_reduction((len(cf) - 1, cf))

+

+    print("Введите коэффициенты второго многочлена:")

+    cf = list(map(int, input().split()))

+    g = poly_reduction((len(cf) - 1, cf))

+

+    f_size = int(input("Введите размерность поля: "))

+

+    q, r = pdf(f, g, f_size)

+

+    print("Результат деления:", poly_print(q))

+    if r is not None:

+        print("Остаток от деления:", poly_print(r))

+    else:

+        print("Остатка нет")

diff --git a/lab15/lab15.py b/lab15/lab15.py
new file mode 100644
index 0000000..fa0a3ef
--- /dev/null
+++ b/lab15/lab15.py
@@ -0,0 +1,81 @@
+def get_all_divisors_brute(n):

+    n = n if n > 0 else -n

+    for i in range(1, int(n / 2) + 1):

+        if n % i == 0:

+            yield i

+    yield n

+

+

+def get_poly_value(i, cf, x):

+    if i == 0:

+        return cf[i]

+    else:

+        value = get_poly_value(i - 1, cf, x)

+        return cf[i] + x * value

+

+

+def divide(n, cfs):

+    new_cfs = [cfs[0]]

+    current = cfs[0]

+

+    for i in cfs[1::]:

+        current = current * n + i

+        new_cfs.append(current)

+

+    if new_cfs[-1] == 0:

+        return True, new_cfs[:-1]

+    else:

+        return False, cfs

+

+

+def horner_schema(poly_cf, dividers={}):

+    divisors = get_all_divisors_brute(poly_cf[-1])

+    for i in divisors:

+        res, cfs = divide(i, poly_cf)

+

+        if res:

+            poly_cf = cfs

+            if i not in dividers.keys():

+                dividers[i] = 1

+            else:

+                dividers[i] += 1

+            return horner_schema(poly_cf, dividers)

+        else:

+            another_res, another_new_cfs = divide(-i, poly_cf)

+            if another_res:

+                poly_cf = another_new_cfs

+                if -i not in dividers.keys():

+                    dividers[-i] = 1

+                else:

+                    dividers[-i] += 1

+                return horner_schema(poly_cf, dividers)

+

+    return poly_cf, dividers

+

+

+def get_roots_from_dict(roots):

+    roots = list(roots.keys())

+    if roots == []:

+        print("Многочлен неприводим")

+    else:

+        print("Список корней многочлена:", roots)

+

+

+if __name__ == "__main__":

+    print('Введите коэффициенты многочлена: ')

+    cf = list(map(int, input().split()))

+    n = len(cf) - 1

+

+    print("================================")

+    print("== Вычисление корней полинома ==")

+    print("================================")

+    _, root_dict = horner_schema(cf)

+    get_roots_from_dict(root_dict)

+

+    print()

+    print("==================================")

+    print("== Вычисление значения полинома ==")

+    print("==================================")

+    x = int(input("Введите x: "))

+    y = get_poly_value(n, cf, x)

+    print(f"Значение полинома в точке {x} = {y}")

diff --git a/lab4/src/main.rs b/lab4/src/main.rs
index 7609af9..ee41b4f 100644
--- a/lab4/src/main.rs
+++ b/lab4/src/main.rs
@@ -1,7 +1,6 @@
 use rug::{Complete, Integer};
 use std::io;
 
-
 fn main() {
     println!("Введите положительное число:");
     let mut p = String::new();
@@ -17,7 +16,7 @@ fn main() {
         Ok(parsed) => parsed.complete(),
         Err(_) => {
             println!("Не удалось считать число");
-            return ()
+            return ();
         }
     };
 
@@ -37,8 +36,7 @@ fn main() {
 
     if is_prime {
         println!("Число {} является простым", &p);
-    }
-    else {
+    } else {
         println!("Число не является простым");
     }
 }
diff --git a/lab8/lab8.py b/lab8/lab8.py
new file mode 100644
index 0000000..522e316
--- /dev/null
+++ b/lab8/lab8.py
@@ -0,0 +1,141 @@
+import math

+

+

+def get_poly_coeffs(a, n):

+    n += 1

+    coeffs = []

+    for j in range(n):

+        coeffs.append(math.factorial(n - 1) // (math.factorial(j) * math.factorial(n - 1 - j)))

+    for i in range(len(coeffs)):

+        coeffs[i] = coeffs[i] * (a ** i)

+    return coeffs

+

+

+def euler_func(value, power=1):

+    if power == 1:

+        return value - 1

+    else:

+        return value ** power - value ** (power - 1)

+

+

+def get_order(n, r):

+    pwr = n

+    cnt = 1

+    while pwr % r != 1:

+        pwr *= n

+        cnt += 1

+    return cnt

+

+

+def check_power(a, n):

+    powered_a = a

+    b = 1

+    while powered_a <= n:

+        if powered_a == n:

+            return True, b

+        powered_a *= a

+        b += 1

+    return False, 0

+

+

+def check_prime(e):

+    for i in range(2, int(math.sqrt(e))):

+        if e % i == 0:

+            return False

+    return True

+

+

+def get_all_divisors_brute(n):

+    for i in range(1, int(n / 2) + 1):

+        if n % i == 0:

+            yield i

+    yield n

+

+

+def get_only_prime_divisors(inp):

+    g = 1

+    prime_divisors = []

+    while g != inp:

+        for i in get_all_divisors_brute(inp):

+            if check_prime(i) and inp % i == 0 and i != 1:

+                inp = inp / i

+                prime_divisors.append(int(i))

+                break

+    return prime_divisors

+

+

+def get_euler(r):

+    p_d = get_only_prime_divisors(r)

+    euler_func_mult = []

+    for el_1 in p_d:

+        el_pw = 0

+        for el_2 in p_d:

+            if el_1 == el_2:

+                el_pw += 1

+        euler_func_mult.append((el_1, el_pw))

+

+    tmp = []

+    for euler_mult in set(euler_func_mult):

+        tmp.append(euler_func(*euler_mult))

+    euler_func_mult = tmp

+

+    phi_value = 1

+    for elem in euler_func_mult:

+        phi_value *= elem

+    return phi_value

+

+

+def check_polinom(a, n):

+    coeffs = get_poly_coeffs(a, n)

+    coeffs.remove(coeffs[0])

+    coeffs[-1] -= a

+    if not(coeffs[-1]):

+        coeffs.remove(coeffs[-1])

+    for cf in coeffs:

+        if cf % n:

+            return False

+    return True

+

+

+def find_smallest_order(n):

+    r = 1

+    while True:

+        r += 1

+        if math.gcd(r, n) != 1:

+            continue

+        o_r = get_order(n, r)

+        if o_r > (math.log2(n)) ** 2:

+            return r

+

+

+def aks_test(n):

+    r = find_smallest_order(n)

+    phi_r = get_euler(r)

+    border = math.floor(math.sqrt(phi_r) * math.log2(n))

+

+    for a in range(2, border):

+        is_powered, b = check_power(a, n)

+

+        if is_powered and b > 1:

+            return False

+

+        if 1 < math.gcd(a, n) < n and a <= r:

+            return False

+

+        if n <= r:

+            return True

+

+        if not check_polinom(a, n):

+            return False

+

+    return True

+

+

+if __name__ == "__main__":

+    print("Введите число n:")

+    n = int(input())

+    result = aks_test(n)

+    if result:

+        print(f"Число {n} является простым")

+    else:

+        print(f"Число не является простым")

diff --git a/lab9/lab9.py b/lab9/lab9.py
new file mode 100644
index 0000000..5024088
--- /dev/null
+++ b/lab9/lab9.py
@@ -0,0 +1,84 @@
+import math

+import random

+

+

+def erathosphene(n):

+    is_prime = [True] * n

+    p = 2

+    while p * p < n:

+        cur = p * p;

+        while cur < n:

+            is_prime[cur] = False;

+            cur += p;

+        while not is_prime[p + 1]:

+            p += 1;

+        p += 1

+    primes = []

+    for i, p in enumerate(is_prime):

+        if p:

+            primes.append(i)

+    return primes[2:]

+

+

+def get_only_prime_divisors(n):

+    factors = []

+    if (n % 2 == 0):

+        factors.append(2)

+

+    while (n % 2 == 0):

+        n = n // 2

+

+    for i in range(3, int(math.sqrt(n)) + 1, 2):

+        if (n % i == 0):

+            factors.append(i)

+

+        while (n % i == 0):

+            n = n // i

+

+    if (n > 2):

+        factors.append(n)

+

+    return factors

+

+

+def lucas_test(n):

+    prev_n = n - 1

+    prime_divisors = get_only_prime_divisors(prev_n)

+    for a in range(2, n):

+        is_prime = True

+        if pow(a, prev_n, n) != 1:

+            continue

+        for q in prime_divisors:

+            if pow(a, prev_n // q, n) == 1:

+                is_prime = False

+                break

+        if is_prime:

+            return True

+    return False

+

+

+def get_random_number(n):

+    while True:

+        number = random.randrange(2 ** (n - 1) + 1, 2 ** n - 1)

+        if number % 2 == 0:

+            continue

+        for divisor in first_primes_list:

+            if number % divisor == 0 and divisor ** 2 <= number:

+                break

+        else:

+            return number

+

+

+def create_prime(n):

+    while True:

+        number = get_random_number(n)

+        if lucas_test(number):

+            return number

+

+

+first_primes_list = erathosphene(500)

+if __name__ == "__main__":

+    print("Введите количество бит генерируемого простого числа:")

+    n = int(input())

+    result = create_prime(n)

+    print(f"Сгенерированное простое число: {result}")

diff --git a/report/lab1/images/test.png b/report/lab1/images/test.png
new file mode 100644
index 0000000..3425735
--- /dev/null
+++ b/report/lab1/images/test.png
diff --git a/report/lab1/lab1.pdf b/report/lab1/lab1.pdf
new file mode 100644
index 0000000..ce1df61
--- /dev/null
+++ b/report/lab1/lab1.pdf
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
--- /dev/null
+++ b/report/lab1/lab1.xdv
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 <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
diff --git a/report/lab10/images/test10.png b/report/lab10/images/test10.png
new file mode 100644
index 0000000..67dfc55
--- /dev/null
+++ b/report/lab10/images/test10.png
diff --git a/report/lab10/lab10.pdf b/report/lab10/lab10.pdf
new file mode 100644
index 0000000..50eed16
--- /dev/null
+++ b/report/lab10/lab10.pdf
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 <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
diff --git a/report/lab11/images/test11.png b/report/lab11/images/test11.png
new file mode 100644
index 0000000..ed4a42f
--- /dev/null
+++ b/report/lab11/images/test11.png
diff --git a/report/lab11/lab11.pdf b/report/lab11/lab11.pdf
new file mode 100644
index 0000000..c4669a0
--- /dev/null
+++ b/report/lab11/lab11.pdf
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 <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
diff --git a/report/lab12/images/test12.png b/report/lab12/images/test12.png
new file mode 100644
index 0000000..6004670
--- /dev/null
+++ b/report/lab12/images/test12.png
diff --git a/report/lab12/lab12.pdf b/report/lab12/lab12.pdf
new file mode 100644
index 0000000..baefde4
--- /dev/null
+++ b/report/lab12/lab12.pdf
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}<b<n$.

+    \item Вычислить $a = b^2\bmod{n}$.

+    \item

+        Проверить число $a$ на гладкость пробными делениями. Если $a$ является

+        $\mathrm{B}$-гладким числом, то есть $a = \prod_{p\in

+        \mathrm{B}}p^{\alpha_{p}\left({b}\right)}$, следует запомнить вектора

+        $\vec{\alpha}(b)$ и $\vec{\varepsilon}(b)$

+    \item

+        Повторять процедуру генерации чисел $b$ до тех пор, пока не

+        будет найдено $h+1$ $\mathrm{B}$-гладких чисел $b_1,...,b_{h+1}$.

+    \item

+        Методом Гаусса найти линейную зависимость среди векторов

+        $\vec{\varepsilon}(b_1), \dots, \vec{\varepsilon}(b_{h+1})$ и положить:

+        \begin{align*}

+        x &= b_{i_1} \dots b_{i_t}\bmod{n} \\

+        y &= \prod_{p \in \mathrm{B}} 

+                p^{\frac{(\alpha_p (b_{i_1}) + \dots + \alpha_p(b_{i_t}))}{2}}\pmod{n}.

+        \end{align*}

+    \item

+        Проверить $x \equiv \pm y \pmod{n}$. Если это так, то повторить

+        процедуру генерации. Если нет, то найдено нетривиальное разложение:

+        \[{\displaystyle n=u\cdot v, u=gcd\left({x+y,n}\right),

+        v=gcd\left({x-y,n}\right).}\]

+\end{enumerate}

+

+

+\section{Реализация}

+\inputminted{python}{../../lab12/lab12.py}

+

+

+\section{Тестирование}

+\begin{figure}[H]

+    \centering

+    \includegraphics[width=0.8\textwidth]{test12.png}

+\end{figure}

+

+\end{document}

diff --git a/report/lab12/maker.sh b/report/lab12/maker.sh
new file mode 100755
index 0000000..e847acf
--- /dev/null
+++ b/report/lab12/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
diff --git a/report/lab13/images/test13.png b/report/lab13/images/test13.png
new file mode 100644
index 0000000..97c5351
--- /dev/null
+++ b/report/lab13/images/test13.png
diff --git a/report/lab13/lab13.pdf b/report/lab13/lab13.pdf
new file mode 100644
index 0000000..db6cbfa
--- /dev/null
+++ b/report/lab13/lab13.pdf
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 <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
diff --git a/report/lab15/images/test15.png b/report/lab15/images/test15.png
new file mode 100644
index 0000000..a607878
--- /dev/null
+++ b/report/lab15/images/test15.png
diff --git a/report/lab15/lab15.pdf b/report/lab15/lab15.pdf
new file mode 100644
index 0000000..dd9c74e
--- /dev/null
+++ b/report/lab15/lab15.pdf
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 <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
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
--- /dev/null
+++ b/report/lab8/images/test8.png
diff --git a/report/lab8/lab8.pdf b/report/lab8/lab8.pdf
new file mode 100644
index 0000000..0ce50b0
--- /dev/null
+++ b/report/lab8/lab8.pdf
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 <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
diff --git a/report/lab9/images/test9.png b/report/lab9/images/test9.png
new file mode 100644
index 0000000..d6bc2e8
--- /dev/null
+++ b/report/lab9/images/test9.png
diff --git a/report/lab9/lab9.pdf b/report/lab9/lab9.pdf
new file mode 100644
index 0000000..ef0efcc
--- /dev/null
+++ b/report/lab9/lab9.pdf
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<a<n}$ и

+\[a^{n-1} \equiv 1 \pmod n\] и для любого простого делителя $q$ числа

+$n-1$

+\[{\displaystyle a^{\frac {n-1}{q}}\not \equiv 1{\pmod {n}}}\] то $n$

+простое.

+

+Если такого числа $a$ не существует, то $n$ — составное число.

+

+Практическая реализация основана на выборе случайного числа в диапазоне значений

+от $2^{b - 1} + 1$ до $2^b - 1$ (где $b$ определяет число бит генерируемого

+простого числа). Далее это число проверяется на наличие небольших простых

+делителей (простые числа меньше 500), и если таких делителей не найдено,

+осуществляется проверка с помощью теста Люка. Если число проходит тест, значит

+оно является сгенерированным простым числом. Если же число не проходит тест или

+у него есть делители среди небольших первых простых чисел, то выбирается другое

+число из этого диапазона, пока выбранное число не будет проходить тест успешно. 

+

+

+\section{Реализация}

+\inputminted{python}{../../lab9/lab9.py}

+

+

+\section{Тестирование}

+\begin{figure}[H]

+    \centering

+    \includegraphics[width=0.8\textwidth]{test9.png}

+\end{figure}

+

+

+

+\end{document}

diff --git a/report/lab9/maker.sh b/report/lab9/maker.sh
new file mode 100755
index 0000000..e847acf
--- /dev/null
+++ b/report/lab9/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