name: Построение оценок эффективности теста простоты Миллера-Рабина
keyword_list: тест Миллера - Рабина простые числа криптография
abstract: В нашей работе мы ставим задачу получить более точные асимптотические оценки вероятности ошибок теста Миллера–Рабина и проверить их экспериментально. Для получения таких оценок мы ввели понятие нетривиального свидетеля простоты, вывели формулы подсчета числа нетривиальных свидетелей простоты для составных чисел произвольного вида и оценили распределение функции вероятности ошибок на различных числовых интервалах. Это позволило количественно оценить вероятность ошибочной классификации составных чисел как вероятно простых в зависимости от длины числа и количества простых факторов, входящих в разложение этих чисел. Для проверки полученных оценок нами был разработан алгоритм вычисления числа нетривиальных свидетелей составных натуральных чисел, основанный на представлении натуральных чисел в виде двух массивов: массива простых делителей рассматриваемого числа и массива степеней, с которыми простые делители входят в разложения этого числа. В приложении к диссертации мы приводим реализацию этого алгоритма на высокоуровневом языке программирования Python. В диссертации приведены новые и актуальные результаты, связанные с характеризацией вероятности ошибок в полиномиальном тесте простоты Миллера–Рабина. Введены и исследованы понятия нетривиального свидетеля простоты, функция частоты свидетелей, выведены формулы для подсчета числа нетривиальных свидетелей, разработан алгоритм вычисления средней частоты на различных числовых интервалах, выведены асимптотические верхние оценки средней частоты, проведены числовые компьютерные эксперименты по проверке асимптотических формул. Методология и методы исследования. В работе над диссертацией использовались общеизвестные методы теории чисел, теории алгоритмов, алгебры и теории языков программирования. Выполнены числовые эксперименты по расчету средней частоты и выполнено сравнение полученных значений с теоретическими верхними оценками, что позволило интерполировать полученные оценки на числах произвольной длины, в том числе и для контроля максимальной вероятности ошибки теста при генерации криптографических ключей.
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: 50.41.01
rubrics.name: Общие вопросы
oecds.code: 01.01.XY
oecds.name: STATISTICS & PROBABILITY
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: Федеральные государственные автономные учреждения