Свойства теоретико-числовых алгоритмов в абстрактных числовых кольцах: магистерская диссертация / Никита Васильевич Кондратёнок; БГУ, Факультет прикладной математики и информатики, Кафедра дискретной математики и алгоритмики; науч. рук. Васьковский М. М.

Abstract

Объект исследования – теоретико-числовые алгоритмы в абстрактных числовых кольцах. В частности теорема Кронекера-Валена, методы автоматического доказательства теорем, криптографические алгоритмы. Цель работы – изучение выполнимости теоремы Кронекера-Валена в различных факториальных кольцах. Разработка метода автоматического доказательства выполнимости или невыполнимости теоремы в конкретном кольце. Так же изучение свойств RSA-криптосистемы в дедекиндовых кольцах. Методы исследования – изучение литературы, методы теории чисел. Область применения – все сферы науки, в которых исследуемая задача имеет применение. Результаты работы изложены в двух главах. Первая глава посвящена изучению аналога RSA-криптосистемы в дедекиндовых кольцах. Изучена применимость метода повторного шифрования, доказан аналог теоремы Винера и других теорем, связанных с ее безопасностью. Показано, что задача факторизации идеала полиномиально сводится к задаче факторизации в целых числах. Вторая глава посвящена теореме Кронекера-Валена. Выделен класс факториальных колец, в которых эта теорема верна. Разработан алгоритм проверки достаточного условия принадлежности факториального кольца этому классу. Используя эти алгоритмы, приведены примеры колец, для которых теорема Кронекера-Валена верна. Разработан метод доказательства невыполнимости теоремы Кронекера-Валена. Доказано, что теорема Кронекера-Валена не выполняется в действительных квадратичных норменно-евклидовых кольцах.