|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Генерация больших простых чисел с сертификатами простотыдипломная работа (Бакалавр)
- Научный руководитель: Борисенко Владимир Витальевич
- Автор: Ифтихори Хайдар
- Тип: Бакалавр
- Организация, в которой проходила защита: Филиал МГУ им. М.В.Ломоносова в г. Душанбе
- Год защиты: 2024
- Аннотация: Генерация больших простых чисел (десятичная запись которых содержит сотни или даже тысячи цифр) используется в алгоритмах кодирования с открытым ключом и электронной подписи. Наиболее часто для этого используются вероятностные тесты простоты, которые не дают доказательства простоты сгенерированного числа (хотя вероятность того, что оно составное, ничтожна). Однако существует метод генерации случайных больших простых чисел, который вместе с простым числом предъявляет и сертификат его простоты, т.е. доказательство, которое может быть легко проверено. Основой сертификата простоты числа p является предъявление первообразного корня по модулю p, т.е. порождающего элемента мультиликативной группы поля вычетов Zp. С помощью этого метода можно порождать большие простые числа за полиномиальное время. Требуется реализовать данный алгоритм и практически исследовать скорость его работы, а также предельные величины генерируемых простых чисел. Например, можно ли за короткое время (не больше часа) предъявить простое число, запись которого содержит 10 тысяч десятичных цифр? Реализация алгоритма должна использовать библиотеку GMP (GNU Multiple Precision) работы с числами произвольной точности. В частности, можно использовать язык программирования Python, в котором эта библиотека встроена в язык.
- Добавил в систему: Борисенко Владимир Витальевич