X Международная студенческая научная конференция Студенческий научный форум - 2018

Под этим названием понимают следующий метод построения всех простых чисел, не превосходящих некоторого заданного числа N. Берем число 2 и выбрасываем все числа кратные 2. Из оставшихся чисел оставляем наименьшее (в данном случае это число 3) и выбрасываем все числа кратные 3, и так далее. Если первое оставшееся число превышает |N|, то работу прекращаем, поскольку все отобранные и оставшиеся числа являются простыми. При этом ни одно простое число в заданном интервале не будет упущено.

Данный метод позволяет строить множество простых чисел, но оннеудобен для проверки простоты заданного числа. Тем не менее, идеярешета и ее обобщения в настоящее время часто используются для “просеивания” множеств чисел, обладающих тем или иным условием. Более того, разрабатываются специальные микропроцессы, на которых операции “просеивания” выполняются очень эффективно.

Реализация проверки простоты на основе Решета Эратосфена.

Пусть - натуральное число, вообще говоря, большое. Оно может быть либо составным, либо простым. Как определить, к какому из этих двух классов относится данное число? Можно попробовать разделить на простые числа из таблицы, составленной с помощью решета Эратосфена и содержащей все простые числа до некоторой границы , определяемой нашими возможностями. Если у есть малые простые делители, то их можно найти таким способом и доказать, что N — составное число.

Проведя исследование данной темы, было выявлено, что выделение простых чисел является сложной задачей математики.

Проверка чисел на простоту всегда является составной частью алгоритмов генерации случайных простых чисел. Действительно, в противном случае нет возможности убедиться в том, что созданное число не является составным. Алгоритмы проверки чисел на простоту можно разделить на вероятностные и детерминированные. Детерминированный алгоритмы всегда действует по одной схеме и гарантированно дает ответ на поставленный вопрос, является ли проверяемое число простым или нет. Вероятностные же методы проверки на простоту использует генератор случайных чисел и лишь с некоторой вероятностью утверждают, что число является простым. Основным преимуществом при этом является значительно более высокая скорость работы в сравнении с детерминированными методами проверки на простоту.

Список использованной литературы

Боревич З. И., Шафаревич И. Р.. Теория чисел. — М.: Наука, 1972;

Виноградов И. М. Основы теории чисел. — 5-е изд. — М.-Л.: Гостехиздат, 1952;

Коблиц Н. Курс теории чисел в криптографии. Москва: Научное изд-во ТВП, 2001;

Черемушкин А.В. Лекции по арифметическим проблемам в криптографии. – М.: МЦНМО.

Код для цитирования: Скопировать