Формула проверки простого числа

Формула проверки простого числа

На этой странице рассмотрим задачи while22 и while23 задачника Абрамяна: определение простоты числа и задача о нахождении наибольшего общего делителя соответственно. Ниже есть форма для проверки числа на простоту, для этого нужно ввести целое положительное число в жёлтое поле и нажать "проверить".

НОД(A, B) = НОД(B, A mod B), если B ≠ 0; НОД(A, 0) = A,

где «mod» обозначает операцию взятия остатка от деления.

Решение этой задачи смотрите на странице наибольший общий делитель.

студент 3 курса, факультет информатики Самарского университета, г.Самара

студент 3 курса, факультет информатики Самарского университета, г.Самара

студент 3 курса, факультет информатики Самарского университета, г.Самара

студент 3 курса, факультет информатики Самарского университета, г.Самара

кандидат физико-математических наук, доцент кафедры прикладной математики,

Самарского университета, г.Самара

В данной работе рассматриваются основные алгоритмы определения простоты числа. Мы сравним их, используя различные критерии, и определим наиболее оптимальный из них. Наконец, мы предложим программную реализацию самого эффективного и распространённого алгоритма.

Основные определения

Введем некоторые определения, которые будут использованы в работе.

Определение 1. Простое число – натуральное (целое положительное) число ℕ, которое имеет ровно два различных натуральных делителя – единицу и самого себя.

Определение 2. Составное число – натуральное (целое положительное) число ℕ, которое не является простым.

Определение 3. Тест простоты – алгоритм, который по заданному натуральному числу ℕ позволяет точно или с некоторой долей вероятности определить, является ли это число простым.

Определение 4. Криптография – наука о методах обеспечения конфиденциальности, целостности данных, аутентификации, а также невозможности отказа от авторства.

1)

2)

Введение

Дискретная математика — важнейшее направление современной математики. Задачи этой дисциплины являются одними из самых трудноразрешимых. Например, решение задачи факторизации, которая заключается в разложении числа на простые множители, на практике сводится к поиску простых чисел, что приводит к проблеме простоты.

Постановка проблемы

Проблема определения простоты числа интересна с научной точки зрения, так как на данный момент не найдено единой аналитической записи для всех простых чисел. С другой стороны, большие простые числа применяются в криптосистемах с открытым ключом, и вопрос определения простоты числа является нетривиальной задачей. Простые методы, такие, как метод перебора, неприменимы для использования на практике из-за того, что требуют много вычислительных и временных ресурсов. Таким образом использование эффективного теста простоты позволяет повысить скорость и надежность алгоритмов в криптографии.

Тесты простоты

Следует отметить, что существующие алгоритмы проверки простоты могут быть разделены на две больших категории: истинные (детерминированные) и вероятностные тесты. Алгоритмы первой категории позволяют точно определить простоту или составность числа. А те, что относятся ко второй категории, позволяют это выяснить, но с некоторой вероятностью ошибки. Многократное их повторение для одного числа, но с разными параметрами, обычно позволяет сделать вероятность ошибки сколь угодно малой величиной.

Перебор делителей

Тип теста: детерминированный

Сложность алгоритма:

Описание: алгоритм тестирования простоты числа путем полного перебора всех возможных потенциальных делителей.

Алгоритм: представлен на рисунке 1 в виде блок-схемы.

Рисунок 1. Алгоритм проверки числа на простоту при помощи перебора делителей.

Практическое применение: в чистом виде не используется из-за сравнительно большой вычислительной сложности. Деление на маленькие простые числа используется как один из шагов во многих тестах.

Теорема Вильсона

Тип теста: детерминированный

Сложность алгоритма:

Описание: натуральное число n > 1— простое число тогда и только тогда, когда (mod n)

Алгоритм: представлен на рисунке 2 в виде блок-схемы.

Рисунок 2. Алгоритм проверки числа на простоту при помощи теоремы Вильсона

Практическое применение: не применяется из-за трудности вычисления

Тест Агравал—Кайал—Саксена (AKS)

Тип теста: детерминированный

Читайте также:  Автоматические настройки интернета лайф

Сложность алгоритма:

Описание: единственны полиномиальный детерминированный алгоритм проверки числа на простоту. Если существует такое что и для любого a от 1 до выполняется сравнение то n – либо простое число, либо степень простого числа.

Алгоритм: представлен на рисунке 3 в виде блок-схемы.

Рисунок 3. Алгоритм проверки числа на простоту при помощи теста AKS

Практическое применение: в качестве детерминированной полиномиальной проверки на простоту.

Критерий Поклингтона

Тип теста: детерминированный

Сложность алгоритма:, где с – положительная константа, , зависящие от выбора алгоритма факторизации.

Описание: пусть n – натуральное число и n-1 имеет простой делитель q, причем . Если найдется целое число a, для которого выполняются условия:

1.(mod n)

2. НОД(

Тогда n является простым числом.

Алгоритм: представлен на рисунке 4 в виде блок-схемы.

Рисунок 4. Алгоритм проверки числа на простоту при помощи критерия Поклингтона

Практическое применение: для получения больших простых чисел с частично известной факторизацией n – 1.

Тест Ферма.

Тип теста: вероятностный

Сложность алгоритма: O(log 2 n × loglog n × logloglog n)

Описание: тест простоты, основанный на малой теореме ферма, которая гласит, что если n – простое число, то для любого целого a выполняется равенство

или делится на нацело.

Алгоритм: представлен на рисунке 5 в виде блок-схемы.

Рисунок 5. Алгоритм проверки числа на простоту при помощи теста Ферма.

Практическое применение: в чистом виде не используется. Лежит в основе многих алгоритмов проверки простоты числа.

Тест Миллера-Рабина

Тип теста: вероятностный

Сложность алгоритма: O(k*log 2 n), k–количество раундов

Описание: пусть n > 2 – натуральное число, тогда представим число n-1 в виде

n-1 = *t , где t – нечетно, а s — неотрицательно. Число a является свидетелем простоты для числа n, если выполняется одно из условий:

или . Количество свидетелей простоты увеличивают достоверность алгоритма.

Алгоритм: представлен на рисунке 6 в виде блок-схемы.

Рисунок 6. Алгоритм проверки числа на простоту при помощи теста Миллера-Рабина.

Практическое применение: используется в криптосистемах с открытым ключом. Позволяет проверить число на простоту за малое время и давать при этом малую вероятность того, что оно окажется псевдопростым.

Тест Соловея — Штрассена

Тип теста: вероятностный

Описание: данный алгоритм характеризуется числом итераций k. В каждой итерации выбирается случайное число a 1, то число n — составное. В противном случае нужно выяснить, справедливо ли сравнение (mod n). Если сравнение не выполняется, то число n — составное. Если оно выполняется, то a – свидетель простоты числа n. Далее следует повторить данную процедуру, используя другое случайное число a. После нахождения количества свидетелей простоты k (число итераций) можно предположить, что n является простым числом с вероятностью .

Рисунок 7. Алгоритм проверки числа на простоту при помощи теста Соловея-Штрассена.

Практическое применение: не используется из-за недостаточной степени достоверности.

Сравнение тестов простоты

Рисунок 8. Сравнение алгоритмов проверки числа на простоту

Была проведена сравнительная характеристика различных алгоритмов определения простоты числа, по результатам которой можно построить график (рисунок 8). Нетрудно заметить, что среди тестов, которые подверглись проверке на быстродействие, самым эффективным оказался тест Миллера-Рабина. Рассмотрим его программную реализацию в виде консольного приложения.

Программная реализация теста Миллера-Рабина

Рисунок 9. Демонстрация программной реализации алгоритма Миллера-Рабина.

Заключение

Подводя итоги, можно констатировать, что были изучены различные алгоритмы определения простоты числа и осуществлён их сравнительный анализ. Проведённые исследования позволяют сделать вывод о том, что тест Миллера-Рабина является наиболее эффективным и универсальным из тех, что были рассмотрены в данной статье.

Список литературы:

  1. Додонова Н.Л. Конспект лекций по дисциплине алгебраические структуры и теория чисел. Самара, 2016
  2. Шнайер, Б.М. Прикладная криптография/ Б.М.Шнайер — ТРИУМФ 2002. – 816 с.

Простые числа – это натуральные числа, большие единицы, которые имеют только два делителя: единицу и само это число.

Читайте также:  Как сделать визитку в адоб фотошоп

Примеры простых чисел: 2 , 3, 5, 7, 11, 13…

(Единица не является простым числом!)

Существует множество задач, связанных с простыми числами, и хотя формулируются они достаточно просто, решить их бывает очень трудно. Некоторые свойства простых чисел еще не открыты. Это побудило немецкого математика Германа Вейля (Wayl, 1885-1955) так охарактеризовать простые числа: «Простые числа – это такие существа, которые всегда склонны прятаться от исследователя».

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

Не будем гнаться за рекордами, а рассмотрим несколько алгоритмов нахождения простых чисел.

Задача 1. Определение простого числа.

Составить программу, которая будет проверять, является ли введенное число простым.

Самый простой путь решения этой задачи – проверить, имеет ли данное число n (n >= 2) делители в интервале [2; n-1]. Если делители есть, число n – составное, если – нет, то – простое. При реализации алгоритма разумно делать проверку на четность введенного числа, поскольку все четные числа делятся на 2 и являются составными числами, то, очевидно, что нет необходимости искать делители для этих чисел. Логическая переменная flag в программе выступает в роли “флаговой” переменной и повышает наглядность программы, так, если flag = true, то n –простое число; если у числа n есть делители, то “флаг выключаем” с помощью оператора присваивания flag:= false, таким образом, если flag = false, то n – составное число.

Задача 2. Нахождение простых чисел в заданном интервале.

Составить программу, которая напечатает все простые числа в заданном интервале [2, m], для m>3 и подсчитает их количество.

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

Будем использовать следующие приемы оптимизации алгоритма:

  1. рассматривать только нечетные числа;
  2. использовать свойство: наименьшее число, на которое делится натуральное число n, не превышает целой части квадратного корня из числа n;
  3. прерывать работу цикла, реализующего поиск делителей числа, при нахождении первого же делителя с помощью процедуры Break, которая реализует немедленный выход из цикла и передает управление оператору, стоящему сразу за оператором цикла.

Как правило, учащиеся сами догадываются о приемах №1 и №3, но не всегда знают, как реализовать в программе досрочное завершение цикла, прием же №2 для них не очевиден, поэтому, возможно, учителю следует остановиться на нем более подробно или же привести полное доказательство этого утверждения.

Счетчик чисел будет находиться в переменной k. Когда очередное простое число найдено, он увеличивается на 1. Простые числа выводятся по 10 в строке, как только значение счетчика становится кратным 10, курсор переводится на новую строку.

Близнецы

Два нечетных простых числа, разнящихся на два, называются близнецами. Близнецами являются, например, числа 5 и 7, 11 и 13, 17 и 19 и т.д. В начале натурального ряда такие пары чисел встречаются достаточно часто, но, по мере того как мы продвигаемся в область больших чисел, их становится все меньше и меньше. Известно, что в первой сотне имеется целых 8 близнецов, дальше они расположены очень неравномерно, их можно обнаружить все реже и реже, гораздо реже, нежели сами простые числа. До сих пор неясно, конечно ли число близнецов. Более того, еще не найден способ, посредством которого можно было бы разрешить эту проблему.

Читайте также:  Жилищная лотерея проверить билет по штрих коду

Задача 3. Поиск пар чисел близнецов.

Написать программу, которая будет находить все числа близнецы в интервале [2; 1000] и подсчитывать количество пар чисел близнецов.

Фактически будем использовать алгоритм и программу Задачи 2. В этом алгоритме нужно использовать дополнительные переменные для хранения двух “последних” простых чисел и проверять условие наличия близнецов – их разность должна быть равна двум.

Задача 4. Нахождение простых чисел в заданном интервале с выводом в выходной файл.

Реализовать алгоритм задачи 2 с выводом простых чисел в выходной файл по 10 в строке. Последняя строка файла должна содержать информацию о количестве простых чисел в заданном интервале.

Задача 5. Приемы оптимизации алгоритма задачи 4.

Оптимизировать алгоритм задачи 4 следующим образом: найденные простые числа записывать в файл, делимость очередного кандидата проверять только на числа из этого файла.

Словесное описание алгоритма:

  1. Вводим правую границу диапазона – m;
  2. Записываем двойку и тройку в файл;
  3. Пока очередное нечетное число i m ), вывести в файл количество простых чисел.

Эратосфеново решето

Греческий математик Эратосфен (275-194 гг. до н.э.) предложил интересный метод нахождения простых чисел в интервале [2; n]. Он написал на папирусе, натянутом на рамку, все числа от 2 до 10000 и прокалывал составные числа. Папирус стал, как решето, которое “просеивает” составные числа, а простые оставляет. Поэтому такой метод называется Эратосфеновым решетом. Рассмотрим подробнее этот метод.

Пусть написаны числа от 2 до n:

Первое неперечеркнутое число в строке является простым. Таким образом, 2 – простое число. Начинаем “просеивание” с него, перечеркивая все числа, которые делятся на 2:

Далее берем следующее по порядку неперечеркнутое число и перечеркиваем все числа, кратные ему и т. д. Таким образом, мы перечеркнем все составные числа, а простые останутся неперечеркнутыми:

Все числа указанного интервала можно рассматривать как множество и в дальнейшем из этого множества будем исключать (отсеивать) все составные числа.

Задача 6. Нахождение простых чисел с помощью решета Эратосфена.

Реализовать алгоритм решета Эратосфена с помощью организации работы с множествами.

Словесное описание алгоритма:

  1. Выделим из первых n натуральных чисел все простые числа (решето Эратосфена).
  2. Вначале формируем множество BeginSet, состоящее из всех целых чисел в диапазоне от 2 до n. Множество PrimerSet будет содержать искомые простые числа.
  3. Затем циклически повторим действия:
  1. взять из BeginSet первое входящее в него число next и поместить его в PrimerSet;
  2. удалить из BeginSet число next и все другие числа, кратные ему, т. е. 2* next, 3* next и т. д.

Цикл повторяется до тех пор, пока множество BeginSet не станет пустым. Программу нельзя использовать для произвольного n, т. к. в любом множестве не может быть больше 256 элементов. (Для расширения интервала простых чисел можно разбить одно большое множество на несколько маленьких, т. е. представить большое множество в виде массива малых множеств. Этот случай рассматривать не будем. Можно предложить наиболее заинтересованным учащимся самостоятельно рассмотреть этот вариант.)

Литература:

  1. Е.В. Андреева Методика обучения основам программирования на уроках информатики. Лекции 1-8. – М.: Педагогический университет «Первое сентября», 2006.
  2. В.А. Дагене, Г.К. Григас, А.Ф. Аугутис 100 задач по программированию. – М.: Просвещение, 1993. — 255 с.
  3. В.В. Фаронов Турбо Паскаль 7.0. Начальный курс. Учебное пособие. – М.: «Нолидж», 1999. — 616 с.
Ссылка на основную публикацию
Умные часы для детей xiaomi mi bunny
Детские смарт-часы Xiaomi, изготовленные из прочного пластика различных оттенков, предназначены для отображения текущего времени и дополнительной информации (например, о пройденной...
Телефон с камерой лучше чем у айфона
В России начинаются продажи смартфонов iPhone XS и iPhone XS Max. Цены в этот раз просто заоблачные — средняя (256...
Телефон с горизонтальной камерой
Сегодня мало кого можно удивить телефоном с двумя основными камерами. А вот сдвоенную фронтальную камеру встретишь далеко не в каждом...
Улучшить качество связи мтс
Усилитель сигнала МТС– специальный прибор, который необходим для того, чтобы предоставлять более сильный сигнал сотовой связи. Невозможно звонить или отправлять...
Adblock detector