Алгоритм проверки на простоту за O (log N)
Проверка на простоту
Чтобы определить, является ли данное число N простым, безусловно, достаточно написать простой цикл поиска делителей числа N:
Данная функция проверки числа на простоту достаточно эффективна — асимптотика ее работы O (sqrt(N)). Однако, иногда в спортивном программировании нужно уметь проверять число на простоту быстрее.
В некоторых случаях, когда требуется выполнять такую проверку для чисел из некоторого диапазона, то целесообразно воспользоваться алгоритмом Решето Эратосфена.
В данной статье я рассмотрю другой способ выполнять единичные проверки на простоту — тест Ферма.
Вероятностный алгоритм за O (log N) с тестом Ферма
Математическое обоснование теста Ферма достаточно хорошо описано здесь.
Я же приведу его конкретную реализацию на C++, а также покажу, как бороться с переполнением типа long long при возведении в степень.
Тест Ферма
Для того, чтобы проверить число N на простоту с достаточно хорошей вероятностью безошибочности, достаточно 100 раз проверить случайное число A тестом Ферма:
Также стоит отметить, что числа A и N должны быть взаимно просты. Если это условие не выполняется, то число N — заведомо непростое.
Отмечу, что данная функция проверки использует функции нахождения НОД, а также быстрого возведения в степень по модулю.
Нахождение НОД
Собственно, в нахождении НОДа двух чисел проблем меньше всего. Воспользуемся алгоритмом Евклида:
Быстрое возведение в степень по модулю
Быстрое возведение в степень (бинарное) известно довольно широко. Отмечу только, что при перемножении двух чисел типа long long может произойти переполнение типа еще до того, как мы возьмем результат по модулю. Поэтому используем функцию двоичного умножения двух чисел также по модулю. Ее смысл очень похож на быстрое возведение в степень.
Точно также как и при возведении в степень, если второй множитель четный, то можно разделить его на 2, и перейти к вычислению произведения чисел A и B/2. Иначе, нужно вычислить произведение чисел A и B — 1.
Источник
Проверка чисел на простоту
Вы будете перенаправлены на Автор24
Проверка чисел на простоту — это алгоритм определения является ли число простым.
Введение
Одним из главных ветвей сегодняшней математики является направление дискретной математики. Проблемы, стоящие перед этой дисциплиной, числятся среди наиболее трудноразрешимых. Можно привести пример решения задачи факторов, согласно которой необходимо разложить число на простые сомножители. Но фактически она заключается в нахождении простых чисел, откуда возникает эта задача.
Основополагающие определения
Главными определениями являются следующие.
Простое число – это натуральное, целое положительное число n, которое делится только на единицу и на себя.
Составным числом называется натуральное, целое положительное число n, не являющееся простым.
Под тестом на простоту понимается алгоритм, согласно которому возможно точно или приблизительно выяснить, принадлежит ли данное натуральное число n к разряду простых.
Под криптографией понимается научное направление о способах, которые обеспечивают конфиденциальность, сохранность данных, а также невозможность отказаться от авторских прав.
Постановка задачи
С точки зрения науки задача, состоящая в диагнозе простое ли число, представляет интерес, поскольку на сегодня не существует единообразной формализованной формы записи простого числа. Но простые числа значительных размеров применяются в криптографических системах с открытым ключом, и проблема выявления простого числа считается нетрадиционной задачей. Не сложные способы, как, например, способ переборки, не годятся для практического применения по причине того, что для них необходимы значительные ресурсы. То есть, применение оптимального метода на простоту числа, даёт возможность увеличить быстродействие и повысить надёжность алгоритмов в криптографических системах.
Готовые работы на аналогичную тему
Тесты простоты
Необходимо заметить, что все известные алгоритмы определения простоты чисел, можно разделить на группы:
- Дающие истинный результат (детерминированные).
- Тесты, позволяющие определить вероятность того, что число окажется простым.
Первая группа алгоритмов даёт возможность сказать простое число или составное. Вторая группа алгоритмов определяет только вероятность отнесения числа к группе простых. Но многочисленный повтор вероятностного алгоритма для одного и того же числа с различными параметрическими характеристиками, как правило, делает величину ошибки очень незначительной.
Переборка делителей
Данный алгоритм относится к первой группе и определяет простоту числа методом полного перебора любых потенциально вероятных делителей. Структура этого метода тестирования изображена на рисунке один.
Рисунок 1. Переборка делителей. Автор24 — интернет-биржа студенческих работ
На практике данный алгоритм в исходном варианте не применяется, так как требует относительно больших вычислительных мощностей. Но разделение на небольшие простые числа применяется в качестве одного из действий в некоторых тестах.
Метод Вильсона
Этот алгоритм тоже относится к первой группе. Натуральное число n больше единицы будет простым только лишь в определённых случаях. Структура алгоритма изображена на рисунке два.
Рисунок 2. Метод Вильсона. Автор24 — интернет-биржа студенческих работ
Этот алгоритм так же мало используется, так как возникают проблемы при большом числе n.
Метод Агравал—Кайал—Саксена (AKS)
Этот тест также первой группы определения простого числа, который основан на полиномах. Когда есть число r, принадлежащее множеству Z, такое что показатель числа n по модулю r, больше логарифма в квадрате n и для каждого a от 1 до корня квадратного их функции Эйлера по r умноженной на логарифм n справедливо равенство (x+a) в степени n тождественно равно x в степени n плюс a по модулю x в степени r минус единица, n, тогда n – или простое число, или является простым числом, возведённым в степень. Блок-схема этого метода изображена на рисунке три.
Рисунок 3. Метод AKS. Автор24 — интернет-биржа студенческих работ
Данный алгоритм применяется как проверка простоты числа первой группы.
Алгоритм Поклингтона
Данный алгоритм так же относится к первой группе. Уровень сложности данного способа можно определить по формуле: La в степени n [a, c]. Здесь с — положительная постоянная, переменная «a» может принимать значения от нуля до единицы включительно.
Алгоритм можно описать следующим образом. Если n является натуральным числом и n – 1 может иметь простой делитель q, где q> корень квадратный из n минус единица, и если можно найти целое число a, причём справедливы два условия:
- a в степени (n-1) по модулю n тождественно равно единице;
- наибольший общий делитель (a в степени n-1/q, -1, n) = 1,
то справедливо утверждение, что n простое число. Блок-схема этого метода изображена на рисунке четыре.
Рисунок 4. Алгоритм Поклингтона. Автор24 — интернет-биржа студенческих работ
Данный способ находит применение на практике при нахождении простых чисел значительных размеров и когда есть частичные данные о факторинге n – 1.
Алгоритм Ферма
Данный способ тестирования на простоту числа считается вероятностным и относится ко второй группе. Данный способ основывается на теореме Ферма. Она формулируется следующим образом: есть число n и если оно является простым, то для любого целого числа а должно выполняться условие: a в степени (n-1) тождественно равно единице по модулю n должно делиться на n без остатка.
Схема этого метода изображена на рисунке пять.
Рисунок 5. Алгоритм Ферма.
На практике этот алгоритм как таковой не применяется, но заложен в основу некоторых других способов, проверяющих простоту чисел.
Алгоритм Миллера-Рабина
Также относится ко второму типу алгоритмов, то есть является вероятностным. Уровень его сложности можно определить по формуле: О (к • lоg2n), где к – это число проходов. Коротко суть метода можно описать так: если n > 2 является натуральным числом, то можно выразить число n –1 как n –1 равно 2 в степени s, умноженное на t , где t является нечётным, а s должно быть положительным. Тогда числовое значение a может выступать как свидетель простоты числа n, при выполнении хотя-бы одного условия:
- a в степени t тождественно равно единице по модулю n;
- существует целое число r
Уровень достоверности алгоритма возрастает при увеличении числа свидетелей, подтверждающих простоту числа.
Блок-схема этого алгоритма изображена на рисунке шесть.
Рисунок 6. Метод проверки простоты числа посредством алгоритма Миллера-Рабина. Автор24 — интернет-биржа студенческих работ
Практическое использование этот метод находит в криптосистемах, где имеется открытый ключ. Даёт возможность выполнить проверку чисел на принадлежность к группе простых за относительно небольшой промежуток времени при достаточно высокой степени вероятности.
Источник
Алгоритм нахождения простых чисел
Оптимизация алгоритма нахождения простых чисел
2 3 5 7 11 13 17 19 23 29 31… $250.000…
Дело было давно, в университете, когда мы начали изучать язык программирования Pascal и домашним заданием стало создание алгоритма нахождения простых чисел.
Алгоритм был придуман и тутже реализован на изучаемом языке. Программа запрашивала у пользователя число N и искала все простые числа до N включительно. После первого успешного теста сразу же возникло непреодолимое желание ввести N = «много». Программа работала, но не так быстро как хотелось бы. Естественно, дело было в многочисленных проверках (порядка N*N/2), поэтому пришлось избавиться от лишних. В итоге получилось 5 похожих алгоритмов каждый из которых работал быстре предыдущего. Недавно захотелось их вспомнить и реализовать, но на этот раз на Python.
Итак, поехали. Первый алгоритм, ударивший в студенческую голову, продемонстрирован в Листинге 1.
Очень быстро понимаешь, что в подсчете делителей каждого числа нет никакой надобности и поэтому переменную k можно освободить от своих обязанностей. Действительно, если хотябы один делитель имеется, то число уже не простое. Смотрим Листинг 2.
Конструкция break позволяет нам завершить выполнение внутреннего цикла и перейти к следующей итерации внешнего.
Далее возникает вопрос: «а зачем делить на 4, если на 2 число не делится?». Приходим к выводу, что искать делители нужно только среди простых чисел не превышающих делимое. Наш алгоритм превращается в… см. Листинг 3.
А потом вспоминаем теорию чисел и понимаем, что переберать надо только числа, не превосходящие корня из искомого. К примеру, если число M имеет делитель pi, то имеется делитель qi, такой, что pi * qi = M. То есть, чтобы найти пару, достаточно найти меньшее. Среди всех пар, предполагаемая пара с максимальным наименьшим — это пара с равными pi и qi, то есть pi * pi = M => pi = sqrt(M). Смотрим Листинг 4.
Код из Листинга 4 при N=10000 выполняется примерно в 1000 раз быстрее, чем самый первый вариант. Есть еще один «ускоритель», проверять только те числа, которые заканчиваются на 1, 3, 7 или 9 (так как остальные очевидно делятся на 2 или 5). Наблюдаем Листинг 5.
В следствии незначительного изменения Листинга 5 получаем небольшую прибавку в скорости:
Итого: Программа из последнего листинга выполняется, примерно, в 1300 раз быстрее первоначального варианта.
Я не ставил перед собой задачи написать программу максимально быстро решающую данную задачу, это скорее демонстрация начинающим программистам того, что правильно составленный алгоритм играет далеко не последнюю роль в оптимизации Ваших программ.
P.S.
Благодаря замечаниям получаем Листинг 7:
при N=10000, поучаем время:
time 1 = 26.24
time 2 = 3.113
time 3 = 0.413
time 4 = 0.096
time 5 = 0.087
time 6 = 0.083
time 7 = 0.053
Результаты при n = 1 000 000:
time 7 = 7.088
time 8 = 1.143
Источник
Проверка числа на простоту
Простых чисел бесконечное множество. В интернете в свободном доступе можно найти таблицы простых чисел до 21 000 000. Существующие методы проверки чисел на простоту очень сложны, не универсальны, поэтому мной разработан еще один способ проверки числа на простоту для чисел больше 10.
Простое число – целое положительное число, которое имеет два различных натуральных делителя: единицу и самого себя, то есть, если число можно разложить на множители значит оно не простое – а составное.
Пусть А – натуральное число, тогда
где Х и Y – натуральные числа.
Мы знаем, что простые числа не четные, и все числа, заканчивающиеся на 5 и 0 кратны пяти, значит, простые числа всегда заканчиваются на 1, 3, 7, 9. Выберем из таблицы умножения примеры, в которых последняя цифра произведения равна 1 или 3 или 7 или 9 (смотрим рисунок).
Получаем, что бы последняя цифра числа А была равна 1 – последние цифры чисел Х и Y должны быть 1 и 1 (1х1=1) или 3 и 7 (3х7=21) или 9 и 9 (9х9=81).
Что бы последняя цифра числа А была равна 3 – последние цифры чисел Х и Y должны быть равны 1 и 3 (1х3=3) или 7 и 9 (7х9=63).
Что бы последняя цифра числа А была равна 7 – последние цифры чисел Х и Y должны быть равны 1 и 7 (1х7=7) или 3 и 9 (3х9=27).
Что бы последняя цифра числа А была равна 9 – последние цифры числе Х и Y должны быть равны 1 и 9 (1х9=9) или 3 и 3 (3х3=9) или 7 и 7 (7х7=49).
Рассмотрим каждую пару последних цифр для Х и Y по отдельности.
Для пары 1 и 1. Пусть Х =х1, где 1 – последняя цифра числа Х, а х – оставшаяся цифровая часть числа Х без последнего числа. Аналогично Y=y1, где 1 — последняя цифра числа Y, а y – оставшаяся цифровая часть числа Y. Тогда . Произведем умножение в столбик.
Получаем, 100*x*y+10*(x+y)+1=A , откуда
Мы получили уравнение с двумя переменными при известном А. Решений данного уравнения множество, но при условии, что х и у – натуральные, количество решений конечно, или вообще их нет в целочисленном выражении. Получается, если решений нет в натуральных числах, то А является простым числом.
Для остальных пар выполняем аналогичные действия и получаем:
Решение полученных уравнений при больших А – задача трудоемкая, поэтому была написана программа для определения простоты числа согласно нашим уравнениям.
Код написан на Visual Basic.
Данный макрос, написанный на Visual Basic, имеет ряд недостатков. Он ограничен вычислительными возможностями excel и при больших числах более 400млн для предположительно простых чисел выдает ошибку о переполнении. Но, для составных чисел, так как алгоритм после нахождения одного из возможных множителей дальше не считает, макрос считает большие числа. Время расчета в VB составляет 1-5 секунд. Так как расчетные уравнения рассчитаны для чисел больших 10, то простота чисел из первого десятка просто добавлена в макрос.
Таким образом, получен математический способ проверки числа на простоту и написан программный код в Visual Basic для его реализации. Но так как вычислительные возможности в Visual Basic ограничены, для проверки простоты больших чисел требуется написание программы на других языках программирования.
Источник