10046

Тест Соловея-Штрассена проверки чисел на простоту

Доклад

Информатика, кибернетика и программирование

Тест Соловея-Штрассена проверки чисел на простоту. При тестировании чисел на простоту с помощью вероятностного теста основанного на малой теореме Ферма может возникнуть ситуация когда вероятность ошибки не снижается с количеством повторений теста. В этом случае ...

Русский

2013-03-20

38.5 KB

34 чел.

Тест Соловея-Штрассена проверки чисел на простоту.

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

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

Вероятностный тест Соловея-Штрассена использует критерий Эйлера для определения значения символа Лежандра: .

Основой теста является следующее утверждение.

 

Теорема. Нечетное целое число является простым тогда и только тогда, когда для всех чисел :  выполняется сравнение вида .

Назовем указанное сравнение соотношением Эйлера.

В этом соотношении левая часть вычисляется непосредственно, а правая часть – по правилам вычисления символа Якоби, который совпадает с символом Лежандра, если число n является простым.

Число , удовлетворяющее соотношению Эйлера, называется эйлеровым псевдопростым по основанию  . Известно, что эйлеровы псевдопростые являются псевдопростыми числами.

Из теоремы следует, что составных чисел, которые были бы эйлеровыми псевдопростыми по любому основанию, не существует.

Тест Соловея-Штрассена аналогичен тесту Ферма.

Псевдослучайно выбираем вычет , проверяем условие . Если условие не выполнено, значит, - составное. Проверяем соотношение Эйлера. Если оно не выполняется, то число - составное. Иначе, повторяем тест для другого значения .

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

Оказывается, при повторении теста Соловея-Штрассена раз, вероятность неотбраковки составного числа .


 

А также другие работы, которые могут Вас заинтересовать

68718. Специфика СсО в политике, коммерческом секторе, общественных объединениях, государственных учреждениях 26.5 KB
  ПР подразделения создаются в министерствах других органах управления. В региональных и муниципальных органах практикуется постоянное общение с гражданами в федеральных органах власти больший упор делают на взаимодействие с прессой на аналитическую и прогностическую деятельность.
68719. Акты толкования права 23.5 KB
  Акт толкования официальный юридически значимый документ направленный на установление действительного смысла нормы права Акты толкования делятся на письменные могут облекаться в форму НПА приказы инструкции и т. Они могут облекаться в ту же форму что и нормативно-правовые акты издаваемые соответствующими...
68722. ОРФОЭПИЧЕСКИЕ НОРМЫ РУССКОГО ЛИТЕРАТУРНОГО ЯЗЫКА 44.03 KB
  Орфоэпия (от греческих слов: orthos - прямой, правильный и epos - речь) - это совокупность правил, устанавливающих единообразное произношение. Орфоэпия указывает, как должны произноситься те или иные звуки в определенных фонетических положениях, в определенных сочетаниях с другими звуками, а также в определенных...
68723. Традиционалистский и техногенный типы цивилизационного развития 25.5 KB
  Понятие цивилизации впервые возникло в 18 веке во Франции для обозначения общества, в котором господствует свобода, равенство и братство. Позднее в исторической и философской литературе под цивилизацией стали понимать различные культурно-исторические типы обществ, объединявших несколько государств...
68724. Инновационный рынок 20.58 KB
  Классификация научных организаций по секторам науки Сектор Содержание Государственный Организации министерств и ведомств которые осуществляют управление государством и удовлетворение потребностей общества в целом: государственная оборона общественный порядок здравоохранение культура социального обеспечения и пр.
68725. Закономерности глобализации мировой экономики и ее воздействие на функционирование национально-государственных систем. Теоретическая проблема экономической безопасности 48 KB
  Одним из ключевых процессов развития мировой экономики на грани ХХ ХХI веков является прогрессирующая глобализация т. Интернационализация хозяйственной деятельности это усиление взаимосвязи и взаимозависимости экономик отдельных стран влияние международных экономических отношений...