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