Заказать работу


Тип работы:
Предмет:
Язык работы:


Улучшение алгоритма кольцевой факторизации для построения простых чисел

Работа №76612
Тип работыДипломные работы, ВКР
Предметматематика
Объем работы65
Год сдачи2019
Стоимость4780 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено 3
Не подходит работа?

Узнай цену на написание

Введение 6
1 Способы поиска простых чисел 8
1.1 Решето Эратосфена 8
1.2 Решето Сундарама 9
1.3 Решето Аткина 10
1.4 Кольцевая факторизация 11
1.5 Способы модификации алгоритмов просеивания простых чисел 13
2 Программная реализация алгоритмов поиска последовательных простых
чисел 14
2.1 Выбор программных средств 14
2.2 Интерфейс приложения 15
2.3 Реализации решета Эратосфена и его модификаций 17
2.4 Реализация и улучшение алгоритма сегментированного решета
Эратосфена с битовым сжатием, кольцевой факторизацией и параллельным просеиванием 24
2.5 Класс измерения времени 32
2.6 Реализация решета Сундарама и его оптимизация 33
2.7 Реализация решета Аткина и его оптимизация 35
3 Сравнительный анализ эффективности реализованных алгоритмов
просеивания 39
Заключение 52
Список использованных источников 54
Приложение


Проблема нахождения простых чисел существует с давних времен. Древнегреческий математик Эратосфен первым предложил эффективный алгоритм нахождения всех простых чисел до заданного числа п. В настоящее время существует множество различных алгоритмов просеивания простых чисел. Наиболее известные из них - это решето Сундарама и решето Аткина.
Современная криптография применяет эти алгоритмы с различными модификациями для генерации последовательных простых чисел. Однако, стоит отметить, что в современной криптографии чаще всего используются комбинации или различные модификации алгоритмов.
Практически вся асимметрично-ключевая криптография базируется на некоторых положениях теории чисел, включая теории, связанные с простыми числами. Большие простые числа являются основой для генерации криптографических ключей, которые используются для проведения защищенных транзакций. В частности, они используются для генерации ключей в самой популярной криптографической системе RSA, в криптосистеме Рабина, Эль-Гамаля и других системах шифрования с открытым ключом. Сами алгоритмы шифрования применяются, например, для аутентификации на вебсайтах, использующих цифровые сертификаты. При помощи ассиметричных шифров также реализуется цифровая подпись.
Поэтому развитие методов поиска и построения простых чисел, основанных на эффективных алгоритмах просеивания, имеет огромное фундаментальное и прикладное значение для решения проблем обеспечения информационной безопасности.
На данный момент наибольшим из известных простых чисел является число Мерсенна М82 589933 = 2 8 2 5 89 93 3 — 1 . Оно содержит 24 862 048 десятичных цифр. А самые большие известные простые близнецы - это . Они состоят из цифр. В мире простых
чисел существует еще много других удивительных рекордов.
Объект исследования в этой работе - алгоритмы последовательного построения простых чисел.
Предмет исследования - способы улучшения алгоритмов последовательного построения простых чисел.
Цель работы - реализовать и улучшить алгоритм кольцевой
факторизации для построения простых чисел на основе решета Эратосфена.
В соответствии с поставленной целью сформулированы следующие задачи:
1. осуществить теоретический анализ различных подходов к поиску простых чисел;
2. выбрать и реализовать наиболее эффективные алгоритмы поиска последовательных простых чисел;
3. реализовать алгоритм кольцевой факторизации на основе решета Эратосфена;
4. улучшить алгоритм кольцевой факторизации;
5. провести сравнительный анализ эффективности реализованных
алгоритмов поиска последовательных простых чисел.
Апробация результатов. Результаты проводимой работы докладывались на:
- XLI студенческой научной конференции ОГУ. Секция «Фундаментальная и прикладная математика» (Оренбург, 2-9 апреля 2019 г.);
Публикации. По теме исследования опубликована одна работа ( [1] в списке использованных источников).
Личный вклад автора. Результаты, выносимые на защиту, получены автором самостоятельно.


Возникли сложности?

Нужна помощь преподавателя?

Помощь в написании студенческих
и аспирантских работ!


Проведенное исследование по теме «Улучшение алгоритма кольцевой факторизации для построения простых чисел» позволяет сделать следующие выводы.
Первая задача, поставленная в данной работе, заключалась в том, чтобы проанализировать различные подходы к поиску простых чисел. В результате выполнения первой задачи установлено, что асимптотически наиболее быстрым является решето Аткина. При этом огромное значение имеет использование различных способов оптимизации алгоритмов просеивания. А лучше всего оптимизациям поддается решето Эратосфена.
Вторая задача, сформулированная в работе, предполагала выбор и реализацию наиболее эффективных алгоритмов поиска простых чисел. При выполнении этой части работы были реализованы и улучшены решета Сундарама, Аткина и Эратосфена. При их оптимизации использовались такие способы как: битовое сжатие, быстрый подсчет нулевых битов, оптимизация на уровне кода. Для решета Аткина также был разработан собственный метод оптимизации алгоритма, учитывающий его особенности. Этот метод меняет структуру основных циклов алгоритма таким образом, что удается полностью избавиться от тяжелых для процессора операций умножения и нахождения остатка от деления в основном теле цикла. Тестирование, проведенное в третьей главе работы, показало, что в режиме компиляции без автоматической оптимизации кода этот метод улучшения решета Аткина дает прирост скорости работы более чем в 10 раз!
Третья задача заключалась в реализации алгоритма кольцевой факторизации на основе решета Эратосфена. В работе был реализован алгоритм кольцевой факторизации 2-го и 3-его порядка. В сочетании с сегментированным решетом был реализован алгоритм кольцевой факторизации 2-го порядка.
Четвертой задачей в работе было улучшение алгоритма кольцевой факторизации. Для сегментированного решета Эратосфена со 2 порядком кольцевой факторизации также было использовано битовое сжатие. Помимо этого, для него был реализован способ быстрого подсчета количества простых чисел, ускоряющий эту часть алгоритма как минимум в 25 раз! Также был разработан и реализован собственный способ улучшения алгоритма, позволяющий снизить расход памяти на хранение базы простых чисел в 4 раза! Использование этого подхода уменьшает общий расход оперативной памяти алгоритмом примерно втрое и делает его практически не ощутимым при просеивании любых 64 битных чисел. Дополнительно ко всем внесенным улучшениям был реализован способ распараллеливания вычислений на все доступные ядра процессора, что позволяет ускорить алгоритм пропорционально количеству физических ядер процессоров в системе.
Провести сравнительный анализ эффективности реализованных алгоритмов по памяти и по времени стало пятой задачей работы. При выполнении этой части работы было проведено тестирование 18 различных реализаций решет. Среди несегментированных алгоритмов наиболее эффективным оказалось решето Эратосфена с 3 порядком кольцевой
факторизации. Но даже решето Эратосфена с 1 порядком кольцевой
факторизации превосходит по скорости работы оптимизированное решето Аткина. Решето Сундарама же многократно уступает всем реализованным алгоритмам. Результаты тестирования также показали, что для просеивания больших простых чисел обязательным является использование сегментированного решета. Среди сегментированных решет оптимальное соотношение скорости работы и объема задействованной оперативной памяти показало решето, использующее компактный способ хранения базы простых чисел. Применение кольцевой факторизации по результатам тестирования оказалось не только очень эффективным методом уменьшения объема потребляемой памяти, а также крайне эффективным способом ускорения работы алгоритма. Прирост в скорости работы оказался даже больше, чем ожидалось из теоретических оценок!



1 Петин, А. Д. Улучшение алгоритма кольцевой факторизации для построения простых чисел, Шаг в науку - № 4, 2019. - С. 1-7.
2 Коутинхо, С. Введение в теорию чисел. Алгоритм RSA, Постмаркет, 2001. - С. 105-109.
3 Sorenson, J. An Introduction to Prime Number Sieves, Department of Computer Sciences University of Wisconsin-Madison, 1990.
4 O'Neill, M. E. The Genuine Sieve of Eratosthenes, Journal of Functional Programming, Published online by Cambridge University, 2008.
5 Pritchard, P. Linear prime-number sieves: a family tree, Sci. Comput. Programming, 1987. P. 17-35.
6 Решето Сундарама [Электронный ресурс]. - 2009. - Режим доступа: https://ru.wikipedia.org/wiki/Решето_Сундарама. - 25.03.2019.
7 Atkin A. O. L., Bernstein D. J. Prime sieves using binary quadratic forms, Math. Comp. 73, 2004.
8 Минаев В. А., Васильев Н. П., Лукьянов В. В., Никонов С. А., Никеров Д. В. Индексные алгоритмы вычисления простых чисел с использованием метода кольцевой факторизации, ВЕСТНИК - № 4, 2013.
9 Минаев В. А., Сычев М. П., Никонов С. А. и Никеров Д. В., Реализация индексных алгоритмов поиска простых чисел с помощью параллельных вычислений, Вестник МГТУ им. Н.Э. Баумана. Серия «Приборостроение». - №6 (105). - 2015.
10 Минаев, В. А. Простые числа: новый взгляд на закономерности формирования, М.: Логос, 2011.
11 Минаев, В. А. Теорема о полном множестве простых чисел. М.: НИЯУ МИФИ, 2011.
12 Обстоятельно о подсчёте единичных битов [Электронный ресурс]. -
2016. - Режим доступа: https://habr.com/ru/post/276957/. - 21.02.2019.
13 Компрессия больших массивов простых чисел [Электронный ресурс]. - 2018. - Режим доступа: https://habr.com/ru/post/417753/. - 07.02.2019.
14 Диамонд, Г. Элементарные методы в изучении распределения простых чисел, УМН 45:2(272), 1990.
15 Постников А. Г., Романов Н. П. Упрощение элементарного доказательства А. Сельберга асимптотического закона распределения простых чисел, УМН, 10:4(66), 1955.
16 Selberg, A. An Elementary Proof of the Prime Number Theorem, Ann. Math. 50, 1949.


Работу высылаем на протяжении 30 минут после оплаты.

Пожалуйста, укажите откуда вы узнали о сайте!



© 2008-2021 Cервис помощи студентам в выполнении работ
.