name: Разработка эффективных алгоритмов вычисления НОД натуральных чисел для криптографии и теории чисел
keyword_list: УСКОРЕНИЕ ВЫЧИСЛЕНИЯ НОД K-АРНЫЙ АЛГОРИТМ НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ
abstract: В диссертации исследуются алгоритмы вычисления наибольшего общего делителя натуральных чисел: алгоритм Евклида, k-арный алгоритм вычисления НОД Д. Соренсона и аппроксимирующий алгоритм Ш.Т. Ишмухаметова. Разработаны методы ускорения указанных алгоритмов, программное обеспечение и методика тестирования указанных алгоритмов, обеспечивающие существенное ускорение указанных алгоритмов. Основными достижениями диссертации являются: 1. Разработка программного комплекса, реализующего рассмотренные алгоритмы и выполняющий оценки их эффективности на языке программирования язык С++ в среде Visual Studio с использованием библиотеки длинных чисел MPIR); 2. Построение оптимальных значений параметров, обеспечивающих быстрое выполнение k-арного и аппроксимирующего алгоритмов для пар чисел различной длины; 3. Выполнены экспериментальные оценки скорости вычисления НОД для чисел различной разрядности для аппроксимирующего k-арного алгоритма, получены численные результаты сходимости этих алгоритмов в виде таблиц и графиков по числу итераций и времени вычислений для чисел различной длины до 2000 десятичных разрядов (примерно, 6500 бит). 4. Разработан новый комбинированный алгоритм КОМБИ вычисления НОД, основанный на сочетании на разных итерациях алгоритмов Евклида и k-арного алгоритма, работающий до двух раз быстрее, чем исходные алгоритмы Евклида и Соренсона.
chairman_dissertation_council.name: Марат
chairman_dissertation_council.surname: Арсланов
chairman_dissertation_council.patronymic: Мирзаевич
chairman_dissertation_council.position: Председатель
chairman_dissertation_council.degree: Доктор физико-математических наук
chairman_dissertation_council.rank: Профессор
chairman_dissertation_council.wos_research_id: D-7271-2015
chairman_dissertation_council.scopus_author_id: 7004438484
chairman_dissertation_council.rinc_id: 2520
chairman_dissertation_council.territory: РОССИЯ
organization_supervisor.name: Данис
organization_supervisor.surname: Нургалиев
organization_supervisor.patronymic: Карлович
organization_supervisor.position: Проректор
organization_supervisor.territory: РОССИЯ
rubrics.code: 83.31.39
rubrics.name: Статистика информатики и вычислительной техники
rubrics.code: 28.25.23
rubrics.name: Кибернетические аспекты структурно-логической теории алгоритмов и программирования
rubrics.code: 27.41.41
rubrics.name: Алгоритмы решения задач вычислительной и дискретной математики
oecds.code: 01.02.EV
oecds.name: COMPUTER SCIENCE, INTERDISCIPLINARY APPLICATIONS
oecds.code: 01.02.ER
oecds.name: COMPUTER SCIENCE, CYBERNETICS
speciality_codes.name: Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей
speciality_codes.code: 05.13.11
supervisors.fio: Ишмухаметов Ш. Т.
supervisors.scientific_degree: Доктор физико-математических наук
supervisors.speciality_code: Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей
supervisors.responsible_type: Научный руководитель
opponents.fio: Дерюгин Ю.Н.
opponents.scientific_degree: Доктор физико-математических наук
opponents.speciality_code: Вычислительная математика
opponents.responsible_type: Оппонент
opponents.fio: Тумбинская М. В.
opponents.scientific_degree: Кандидат технических наук
opponents.speciality_code: Управление в социальных и экономических системах
opponents.responsible_type: Оппонент
protection_organization.short_name: ФГАОУ ВО "КАЗАНСКИЙ (ПРИВОЛЖСКИЙ) ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ", ФГАОУ ВО КФУ, КФУ, КАЗАНСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ, КАЗАНСКИЙ УНИВЕРСИТЕТ, КАЗАНСКИЙ (ПРИВОЛЖСКИЙ) ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ
protection_organization.name: ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ "КАЗАНСКИЙ (ПРИВОЛЖСКИЙ) ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ"
protection_organization.ogrn: 1021602841391
protection_organization.supervisor_name: ИЛЬШАТ
protection_organization.supervisor_surname: ГАФУРОВ
protection_organization.supervisor_patronymic: РАФКАТОВИЧ
protection_organization.organization_type: Организация
protection_organization.okogu: Министерство науки и высшего образования Российской Федерации
protection_organization.okopf: Федеральные государственные автономные учреждения
author_organization.short_name: ФГАОУ ВО "КАЗАНСКИЙ (ПРИВОЛЖСКИЙ) ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ", ФГАОУ ВО КФУ, КФУ, КАЗАНСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ, КАЗАНСКИЙ УНИВЕРСИТЕТ, КАЗАНСКИЙ (ПРИВОЛЖСКИЙ) ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ
author_organization.name: ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ "КАЗАНСКИЙ (ПРИВОЛЖСКИЙ) ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ"
author_organization.ogrn: 1021602841391
author_organization.supervisor_name: ИЛЬШАТ
author_organization.supervisor_surname: ГАФУРОВ
author_organization.supervisor_patronymic: РАФКАТОВИЧ
author_organization.organization_type: Организация
author_organization.okogu: Министерство науки и высшего образования Российской Федерации
author_organization.okopf: Федеральные государственные автономные учреждения