Как найти простое число программа

Содержание

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

Метод «грубой силы»: просто, но медленно

Если чисел немного и они на слишком велики, то вполне годится «метод грубой силы»: пробуем делить наше число на все числа меньше его. Если не найдется чисел, на которые наше число делится без остатка, то оно простое.

Приведем фрагмент программы, который осуществляет проверку числа n:

prime = True
for i in range(2,n):
if n%i == 0:
prime = False
break

По завершении цикла переменная prime будет иметь значение True, если число n простое, и False в противном случае.

Процедуру можно существенно ускорить, если проверять делимость на числа в диапазоне от 2 до квадратного корня из проверяемого числа. Можно также отдельно проверить делимость на 2, а потом — только на нечетные числа.

Простые числа (Python)

Улучшенный код выглядит так:

prime = True
if n%2 == 0 and n > 3:
prime = False
else:
i=3;
while i*i if n%i == 0:
prime = False
break
i += 2

Второй вариант работает гораздо быстрее. Например, для проверки на простоту чисел от 2 до 100000 первому варианту потребовалось около 38 секунд, а второму — всего 0,35 секунды. Поэтому второй вариант — вполне рабочий.

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

Как составить таблицу простых чисел?

Программа составления массива простых чисел не так уж и сложна. Приведем соответствующий фрагмент кода.

limit = 1000000
primes=[2]
for n in range(3,limit+1,2):
k=0
prime = True
while primes[k]*primes[k] if n%primes[k] == 0:
prime = False
break
k += 1
if prime: primes.append(n)

В переменной limit задается верхний предел поиска простых чисел: после завершения в массив primes будут помещены все простые числа, не превосходящие значение limit.

Вначале помещаем в массив primes число 2 — единственное четное простое число. В дальнейшем будем проверять лишь нечетные числа. Это делается в цикле, в котором переменная n принимает все нечетные значения, начиная с трех и не превосходящие заданного предела.

Для каждого нечетного числа проверяется его делимость на все найденные ранее простые числа, не превосходящие корня из данного числа. Если проверяемое число разделится на какое-либо из простых чисел без остатка, то это число — составное. В противном случае число — простое, оно добавляется в массив primes.

Программа работает достаточно быстро: все простые числа, не превосходящие миллиона, находятся примерно за 5 секунд.

Источник: ege-informatika-yk.blogspot.com

Как узнать простое число или нет?

Русские Блоги

Наверное, самый эффективный алгоритм поиска простых чисел

Это название немного шокирует. Сначала по коду:
Версия C ++:

#include using namespace std; int prime(int n); int main() < prime(100); return 0; >int prime(int n) < int i; bool *prime = new bool[n+1]; for(i=2;ifor(i=2;i <=n;i++)< if(prime[i])< cout<> > cout
#coding=UTF-8 n = 100 sum = 0 prime = [] for i in range(n+1): prime.append(True) for i in range(2,n+1): if prime[i]: print i, j = i+i while j

Кажется, это просто, но сложно понять?

Давайте посмотрим на блог Великого Бога, который передан из блога Programming Caprice.https://program-think.blogspot.com/2011/12/prime-algorithm-1.html, После переформатирования, а? Ссылку открыть нельзя? Кеке, ты знаешь, просто посмотри сюда. Исходный текст длинноват, но если вы можете продолжать его читать (автор оригинального текста все еще довольно юмористический), вы обязательно его поймете, а предыдущая программа довольно проста для понимания.

оригинал:

Позавчера (примечание перевозчика: вероятно, однажды в 2011 году) я был в «Мой опыт приема на работу [4]: Что можно увидеть, выполнив письменный тест?В статье, посвященной поиску простых чисел, в качестве примера вводится некоторый опыт исследования кандидатов. Поскольку в этой статье нет политически чувствительного содержания, я, кстати, перепосту ее в своем зеркальном блоге на CSDN.
Вчера пользователь сети CSDN написал в сообщении:

Если честно, эту программу нелегко написать, если вы не запомните этот код.

Если вы попросите других писать программы на бумаге, многие люди сделают ошибки.

Но если вы отдадите его компьютеру, большинство людей отладят эту программу правильно.

Бессмысленно спрашивать в этой теме

Вы можете только заставить других думать, что у вас мало вопросов

Во-первых, этот пользователь сети может невнимательно читать пост. В статье я специально подчеркнул, что при оценке ответов на письменный тест «мышление и мышление» гораздо важнее, чем «правильно или неправильно», и он / она все еще не понимает, что правильно или неправильно; во-вторых, этот пользователь сети на самом деле думает, что этот вопрос — ничто. То есть почему мне от этого плохо? ! Похоже, что многие пользователи сети вообще не уловили загадки!
Забудьте об этом, я откажусь от этого сегодня и встряхну всех с тяжести этой темы. Разумеется, в результате этого бремя пошатнулось: начиная с сегодняшнего дня вопрос о «поиске простых чисел» должен быть удален из письменного теста моей компании, а затем заменен другим, совершенно другим. Я терпеть не могу отнять такой хороший вопрос 🙁

★ Название

Хорошо, вернемся к делу. Далее я проанализирую загадку этой темы под разными углами, от более мелких до более глубоких.
Во избежание обвинений в «игре в слова» (некоторые учащиеся сами не рассматривают вопросы, а жалуются, что человек, написавший вопросы, играет в словесные игры), перед тем, как представить различные области, пожалуйста, будьте ясны Смысл вопроса.
Как упоминалось в предыдущем сообщении, есть два следующих способа найти простые числа.

◇ Спрос 1

Пожалуйста, реализуйте функцию. Для данного целочисленного параметра N функция может печатать простые числа меньше N в натуральных числах от малого до большого.
Например, если N = 10, распечатать

◇ Требование 2

Пожалуйста, реализуйте функцию. Для данного целочисленного параметра N функция может распечатать наименьшие N простых чисел натуральных чисел в последовательности от малого к большому.
Например, если N = 10, распечатать

2 3 5 7 11 13 17 19 23 29

★ Пробное отделение

Первое, что я хочу представить, это, конечно же, «пробное деление». Учитывая, что некоторые читатели — новички, немного поясните.
«Пробное разделение», как следует из названия, означает постоянные попытки разделить его. Например, чтобы определить, является ли натуральное число x простым числом, мы продолжаем пробовать натуральные числа, которые меньше x и больше 1. Пока одно делится на единицу, x является составным числом; в противном случае x является простым числом.
Очевидно, пробное разделение — это самая простая идея. Говоря прямо, это тоже самая посредственная идея. Но, черт возьми, у этого самого посредственного образа мышления много сфер. Пожалуйста, смотрите:

◇ Царство 1

В пробном делении самый приземленный путь:
Предполагая, что для определения того, является ли x простым числом, попробуйте от 2 до x-1. Такой подход должен быть худшим по эффективности. Если в этом вопросе 10 баллов, даже если подобный код правильный, я дам только 1 балл.

◇ Царство 2

Чуть более умный программист подумает: если у x есть простой фактор (отличный от него самого), он определенно будет меньше или равен x / 2, так что ущипните, они просто попробуют от 2 до x / 2.
Это половина рабочей нагрузки, но все же глупый способ. Для начисления очков, даже если код правильный, всего 2 балла

◇ Мир 3

Более сообразительный программист мог бы подумать: кроме 2, все возможные простые множители нечетны. Итак, они сначала пробуют 2, а затем пробуют все нечетные числа от 3 до x / 2.
На этот раз рабочая нагрузка уменьшена вдвое. Однако должен сказать, что он все же очень приземленный. Даже если код полностью верен, вы получите только 3 балла.

◇ Царство 4

Умнее, чем первые три типа программистов, и вы убедитесь в этом: на самом деле, пока вы пытаетесь от 2 до √x, он будет работать. Подсчитано, что некоторые пользователи сети не могут понять этого, почему им нужно только достичь √x?
кратко объясните: все факторы появляются парами. Например, множители 100: 1 и 100, 2 и 50, 4 и 25, 5 и 20, 10 и 10. Видишь? Пара множителей, один из которых должен быть меньше или равен квадратному корню из 100, а другой больше или равен квадратному корню из 100. Что касается строгого математического доказательства, его можно сделать со знанием математики в начальной школе, так что я не буду слишком многословен.

◇ Царство 5

Итак, если вы сначала попробуете 2, а затем попытаетесь разделить все нечетные числа от 3 до √x, достаточно ли этого? Ответ явно отрицательный? Пока только начал разогреваться.
некоторые более сообразительные программисты обнаружат проблему: пробовать все нечетные числа от 3 до √x все еще немного расточительно. Например, если вы хотите определить, является ли 101 простым числом, а корень из 101 округляется до 10, то в соответствии с областью 4 нужно попробовать следующие нечетные числа: 3, 5, 7 и 9. Но вы не узнаете. Пробовать 9 излишне. Оно не делится на 3 и не должно делиться на 9 . Следуйте этой линии мышления, и эти программисты обнаружат, что: Фактически, просто попробуйте простое число меньше √x. И эти простые числа были вычислены только что (как вы думаете, это замечательно?).
Таким образом, программист в этом состоянии сначала сохранит вычисленные простые числа, а затем использует их для последующего пробного исключения, что значительно повышает эффективность.
Кстати, это то, что часто упоминается в теории алгоритмов: обмен пространства на время.

◇ Дополнительное объяснение

Четыре состояния в начале в основном прогрессивны. Однако Царство 5 и Царство 4 равны. Среди исследованных мною кандидатов некоторые люди думали о сфере 4, но не думали о сфере 5; напротив, некоторые люди думали о сфере 5, но не думали о сфере 4. Обычно, пока можно думать об одной из этих двух сфер, я даю 5-7 баллов; если продумываются оба, я даю 8-10 баллов.
На позицию «младшего инженера-программиста», которую я хочу нанять, должно быть достаточно думать о сфере 4 и сфере 5 одновременно. Если не требовательны к себе, довольствуйтесь вкусом. Затем, когда вы это увидите, вы можете остановиться, не нужно читать последующий контент; наоборот, если вам больше любопытно или вы хотите узнать больше, продолжайте читать.

★ Метод просеивания

После разговора о «пробном делении» давайте поговорим о методе сита (Википедия объясняет «здесь»). С таким же успехом могу предположить: читателей этой статьи должно быть более 2/3, никогда не слышавших о методе сита. Так что щепотка, кстати, расскажи всем о происхождении ситового метода.
Этот метод сита — действительно умный и быстрый метод поиска простых чисел. Его изобретателем был Эратосфен, великий греческий бык, живший около 250 г. до н. Э. Почему вы говорите, что он большая корова? Потому что он сам владеет многими дисциплинами и областями, включая, по крайней мере, математику, астрономию, географию (термин, который он создал), историю и литературу (он поэт). Это действительно «кросс-полевая большая корова».
Больше всего его восхищало то, что он использовал только простые геометрические методы для измерения окружности Земли, расстояния между Землей и Луной, расстояния между Землей и Солнцем, экватором и эклиптикой. Угол . Более того, эти результаты расчетов мало чем отличаются от тех, которые измеряют современные ученые. Вы знаете, что возраст, в котором он жил, вероятно, эквивалентен периоду весны и осени в Китае. И наши предки упорно не верили до династии Мин: небо круглое, земля квадратная, и луна будет съедено тенгу .
Хорошо, я закончил говорить, давайте вернемся к делу.
Предполагается, что многие люди рассматривают метод сита как отдельный метод. На самом деле метод сита по-прежнему остается очень универсальной идеей. Имея дело со многими сложными проблемами, вы можете увидеть тень метода сита. Итак, как найти простые числа методом сита, очень просто сказать:
Прежде всего, 2 — это распознанное наименьшее простое число, поэтому сначала удалите все числа, кратные 2; затем среди оставшихся чисел больше 2 наименьшее — 3, поэтому 3 также является простым числом; Затем удалите все числа, кратные 3, и среди оставшихся чисел больше 3 наименьшее — 5, поэтому 5 также является простым числом .
Вышеупомянутый процесс повторяется непрерывно, и все составные числа в определенном диапазоне могут быть удалены (как отсеивание), а остальное — простое число. В Википедии есть очень яркая анимация, которая может интуитивно отражать рабочий процесс метода скрининга.
Не видите изображение, пожалуйста, FQ (не паникуйте, движущийся добавит его всем, как показано ниже)

Понимая принцип «ситового метода», каждый должен видеть, что скорость ситового метода значительно лучше, чем «пробного деления». Конечно, программная реализация метода сита также разделена на разные области. Более того, метод сита может быть более сложным. Ниже я расскажу об особенностях метода скрининга с разных сторон.

◇ Как определить диапазон распределения простых чисел?

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

Требование 1

Для спроса 1 это, естественно, не проблема. Поскольку в Требовании 1 диапазон распределения простых чисел равен N, что уже задано и с ним легко справиться.

Требование 2

Но для требования 2 это сложно. Поскольку N, указанное в требовании 2, представляет количество простых чисел, которые необходимо напечатать, то насколько велики распределены N простых чисел? Это головная боль.
Однако, если программисты, претендующие на вакансию, достаточно хороши, конечно, они не будут озадачены этим вопросом. Поскольку распределение простых чисел имеет регулярный образец, это известная теорема о простых числах.
немного разбираетесь в математике, вы должны знать, что простые числа распределяются реже. Другими словами, плотность простых чисел становится все меньше и меньше. Говоря прямо, теорема о простых числах означает, что математики нашли некоторые формулы для оценки количества простых чисел в определенном диапазоне. Среди этих формул наиболее лаконичной является x / ln (x).

◇ Как спроектировать контейнер для хранения?

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

Царство 1

Как обычно, поговорим о самом простом способе — напрямую сконструировать целочисленный контейнер. В процессе просеивания найденные составные числа удаляются, и, наконец, в контейнере остаются только простые числа.
Почему вы считаете этот вид уловок наиболее популярным?
Во-первых, целочисленные контейнеры тратят пространство памяти. Например, если вы используете 32-битный C / C ++ или Java, каждый int использует не менее 4 байтов памяти. Когда N велико, накладные расходы на память становятся проблемой.
Во-вторых, когда N очень велико, частое удаление большого контейнера может привести к частому выделению и освобождению памяти (в зависимости от реализации контейнера); и частое Выделение / освобождение памяти вызовет значительную загрузку ЦП и может вызвать фрагментацию памяти.

Царство 2

Чтобы избежать недостатков, вызванных областью 1, более сообразительные программисты будут создавать логический контейнер фиксированной длины (обычно массив). Например, если диапазон распределения простых чисел равен 1 000 000, создайте массив, содержащий 1 000 000 логических значений. Затем инициализируйте все элементы значением true. В процессе сита, как только определенное натуральное число оказывается составным числом, натуральное число используется в качестве нижнего индекса, а соответствующее логическое значение изменяется на ложное.
После того, как все будет просеяно, просмотрите массив, найдите те элементы, значение которых истинно, и распечатайте их индексы.
Преимущества этой области: во-первых, поскольку контейнер имеет фиксированную длину, во время операции избегается частое выделение / освобождение памяти; во-вторых, в некоторых языках используется логическое значение Он занимает меньше места, чем целочисленные типы. Например, в C ++ bool используется только 1 байт.
Примечание. Стандарт C ++ (ISO / IEC 14882) не требует sizeof (bool) == 1, но большинство компиляторов реализуют его как один байт.

Царство 3

Хотя Realm 2 решает недостатки Realm 1, есть еще много возможностей для оптимизации. Некоторые программисты придумают идею хранения битов. На самом деле это оптимизированная космическая производительность на основе Realm 2. Думаю, об этом легче думать, если вы родились на C / C ++ или играли на ассемблере.
В качестве примера возьмем C ++. Логическое значение занимает 1 байт памяти. И 1 байт имеет 8 бит, и каждый бит может представлять 0 или 1. Итак, когда вы используете побитовое хранилище, один байт можно использовать как 8 логических значений. Следовательно, программист, достигший этого состояния, создаст массив байтов фиксированной длины, и каждый байт массива хранит 8 логических значений. По сравнению с Realm 2 производительность по пространству увеличена в 8 раз (для C ++). Если в определенном языке для представления логического типа используется 4 байта, то область 3 в 32 раза эффективнее, чем область 2.

★ Резюме

Увидев, что я написал слово «резюме», многие пользователи сети подумали: прочитав его, они знают, как находить простые числа, чтобы быть лучшими.
На самом деле, вы снова ошибаетесь, и эта статья написана менее чем наполовину. Учитывая, что пространство уже немного длинновато, и я немного устал после того, как набрал так много слов, я временно прекращаю болтовню и продолжаю говорить в следующий раз.
Я надеюсь, что, прочитав сегодня это введение, каждый должен понять одну истину: за горой есть гора, а за небом — небо. Есть много путей и загадок в каждой маленькой отрасли в любой области техники. Если вы углубитесь в это, вы наверняка многому научитесь. Процесс глубокого исследования — это процесс улучшения ваших способностей.
В следующем содержании этой статьи будут представлены недостатки только что упомянутого метода поразрядного хранения и способы их устранения. Кроме того, будут представлены некоторые другие методы поиска простых чисел.

Хорошо, это конец исходного текста

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

Маленькие мысли

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

Источник: russianblogs.com

Алгоритмы поиска простых чисел

«Самое большое простое число 2 32582657 -1. И я с гордостью утверждаю, что запомнил все его цифры… в двоичной форме».
Карл Померанс

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

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

Решето Эратосфена — алгоритм, предложенный древнегреческим математиком Эратосфеном. Этот метод позволяет найти все простые числа меньше заданного числа n. Суть метода заключается в следующем. Возьмем набор чисел от 2 до n.

Вычеркнем из набора (отсеим) все числа делящиеся на 2, кроме 2. Перейдем к следующему «не отсеянному» числу — 3, снова вычеркиваем все что делится на 3. Переходим к следующему оставшемуся числу — 5 и так далее до тех пор пока мы не дойдем до n. После выполнения вышеописанных действий, в изначальном списке останутся только простые числа.

Алгоритм можно несколько оптимизировать. Так как один из делителей составного числа n обязательно , алгоритм можно останавливать, после вычеркивания чисел делящихся на .

Иллюстрация работы алгоритма из Википедии:

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

Существует ряд оптимизаций, позволяющих снизить эти показатели. Прием под названием wheel factorization состоит в том, чтобы включать в изначальный список только числа взаимно простые с несколькими первыми простыми числами (например меньше 30). В теории предлагается брать первые простые примерно до . Это позволяет снизить сложность алгоритма в раз. Помимо этого для уменьшения потребляемой памяти используется так называемое сегментирование. Изначальный набор чисел делится на сегменты размером и для каждого сегмента решето Эратосфена применяется по отдельности. Потребление памяти снижается до .

Решето Аткина

Более совершенный алгоритм отсеивания составных чисел был предложен Аткином и Берштайном и получил название Решето Аткина. Этот способ основан на следующих трех свойствах простых чисел.

Если n — положительное число, не кратное квадрату простого числа и такое, что . То n — простое, тогда и только тогда, когда число корней уравнения нечетно.

Доказательства этих свойств приводятся в этой статье.

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

Из описания алгоритма следует, что вычислительная сложность решета Аткина и потребление памяти составляют . При использовании wheel factorization и сегментирования оценка сложности алгоритма снижается до , а потребление памяти до .

Числа Мерсенна и тест Люка-Лемера

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

Один из таких методов проверки — тест Люка-Лемера. Это детерминированный и безусловный тест простоты. Это означает, что прохождение теста гарантирует простоту числа. К сожалению, тест предназначен только для чисел особого вида , где p — натуральное число. Такие числа называются числами Мерсенна.

Тест Люка-Лемера утверждает, что число Мерсенна простое тогда и только тогда, когда p — простое и делит нацело -й член последовательности задаваемой рекуррентно: для .

Для числа длиной p бит вычислительная сложность алгоритма составляет .

Благодаря простоте и детерминированности теста, самые большие известные простые числа — числа Мерсенна. Самое большое известное простое число на сегодня — , его десятичная запись состоит из 24,862,048 цифр. Полюбоваться на эту красоту можно здесь.

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

Простых чисел Мерсенна известно не очень много, поэтому для криптографии с открытым ключом необходим другой способ поиска простых чисел. Одним из таким способов является тест простоты Ферма. Он основан на малой теореме Ферма, которая гласит, что если n — простое число, то для любого a, которое не делится на n, выполняется равенство . Доказательство теоремы можно найти на Википедии.

Тест простоты Ферма — вероятностный тест, который заключается в переборе нескольких значений a, если хотя бы для одного из них выполняется неравенство , то число n — составное. В противном случае, n — вероятно простое. Чем больше значений a использовано в тесте, тем выше вероятность того, что n — простое.

К сожалению, существуют такие составные числа n, для которых сравнение выполняется для всех a взаимно простых с n. Такие числа называются числам Кармайкла. Составные числа, которые успешно проходят тест Ферма, называются псевдопростыми Ферма. Количество псевдопростых Ферма бесконечно, поэтому тест Ферма — не самый надежный способ определения простых чисел.

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

Более надежных результатов можно добиться комбинируя малую теорему Ферма и тот факт, что для простого числа p не существует других корней уравнения , кроме 1 и -1. Тест Миллера-Рабина перебирает несколько значений a и проверяет выполнение следующих условий.

Пусть p — простое число и , тогда для любого a справедливо хотя бы одно из условий:

Существует целое число r < sтакое, что

Чем больше свидетелей простоты найдено, тем выше вероятность того, что n — простое. Согласно теореме Рабина вероятность того, что случайно выбранное число a окажется свидетелем простоты составного числа составляет приблизительно .

Следовательно, если проверить k случайных чисел a, то вероятность принять составное число за простое .

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

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

Он смог сгенерировать такие составные числа, которые успершно прошли тест на простоту в библиотеках OpenSSL, CryptLib, JavaScript Big Number и многих других.

Тест Люка и Тест Baillie–PSW

Чтобы избежать уязвимости, связанные с ситуациями, когда сгенерированное злоумышленником составное число, выдается за простое, Мартин Альбрехт предлагает использовать тест Baillie–PSW. Несмотря на то, что тест Baillie–PSW является вероятностным, на сегодняшний день не найдено ни одно составное число, которое успешно проходит этот тест. За нахождение подобного числа в 1980 году авторы алгоритма пообещали вознаграждение в размере $30. Приз пока так и не был востребован.

Ряд исследователей проверили все числа до и не обнаружили ни одного составного числа, прошедшего тест Baillie–PSW. Поэтому, для чисел меньше тест считается детерминированным.

Суть теста сводится к последовательной проверке числа на простоу двумя различными методами. Один из этих методов уже описанный выше тест Миллера-Рабина. Второй — тест Люка на сильную псевдопростоту.

Тест Люка на сильную псевдопростоту

Последовательности Люка — пары рекуррентных последовательностей , описываемые выражениями:

Пусть и — последовательности Люка, где целые числа P и Q удовлетворяют условию

Вычислим символ Якоби: .

Найдем такие r, s для которых выполняется равенство

Для простого числа n выполняется одно из следующих условий:

n делит
n делит для некоторого j < r

Вероятность того, что составное число n успешно пройдет тест Люка для заданной пары параметров P, Q не превышает 4/15. Следовательно, после применения теста k раз, эта вероятность составляет .

Тесты Миллера-Рабина и Люка производят не пересекающиеся множества псевдопростых чисел, соответственно если число p прошло оба теста, оно простое. Именно на этом свойстве основывается тест Baillie–PSW.

В зависимости от поставленной задачи, могут использоваться различные методы поиска простых чисел. К примеру, при поиске больших простых чисел Мерсенна, сперва, при помощи решета Эратосфена или Аткина определяется список простых чисел до некоторой границы, предположим, до . Затем для каждого числа p из списка, с помощью теста Люка-Лемера, на простоту проверяется .

Чтобы сгенерировать большое простое число в криптографических целях, выбирается случайное число a и проверяется тестом Миллера-Рабина или более надежным Baillie–PSW. Согласно теореме о распределении простых чисел, у случайно выбранного числа от 1 до n шанс оказаться простым примерно равен . Следовательно, чтобы найти простое число размером 1024 бита, достаточно перебрать около тысячи вариантов.

Источник: temofeev.ru