diff options
46 files changed, 1631 insertions, 66 deletions
@@ -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 Binary files differnew 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 Binary files differnew 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 Binary files differnew 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 Binary files differnew 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 Binary files differnew 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 Binary files differnew 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 Binary files differnew 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 Binary files differnew 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 Binary files differnew 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 Binary files differnew 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 Binary files differnew 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 Binary files differnew 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 Binary files differnew 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 Binary files differnew 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 Binary files differnew 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 Binary files differnew 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 Binary files differnew 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 |
