10046

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

Доклад

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

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

Русский

2013-03-20

38.5 KB

34 чел.

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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


 

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

35956. Обратимые и необратимые реакции 99.5 KB
  Химическое равновесие Некоторые химические реакции могут протекать в двух взаимно противоположных направлениях. Такие реакции называются обратимыми. Обратимость химических реакций записывается следующим образом: А В  В При протекании химической реакции концентрации исходных веществ уменьшаются в соответствии с законом действия масс.
35959. Химический состав винограда. Свойства и влияние отдельных групп соединений, а также продуктов их превращений на качество вина 93.94 KB
  Свойства и влияние отдельных групп соединений а также продуктов их превращений на качество вина. Эти соединения придают красным виноградным винам лечебные свойства. В белых виноградных винах содержатся только нефланоидные полифенолы. Поэтому содержание полезных для здоровья веществ в белых винах намного ниже чем в красных.
35961. Подходы к принятию инвестиционных решений на фондовом рынке: фундаментальный и технический анализ 94.14 KB
  Управление проектами это методология планирования организации и координации трудовых финансовых и материальнотехнических ресурсов на протяжении проектного цикла направленные на эффективное достижение целей проекта путем применение современных методов техники и технологий управления для достижения определенных в проекте результатов по составу и объему работ стоимости времени качеству и удовлетворению участников проекта. Точечные факторы факторы связанные с реализацией инвестиционного проекта и состоянием реципиента инвестиции....
35963. Неогей 92 KB
  Башкирский антиклинорий сложен почти не метаморфизованными терригеннокарбонатными отложениями рифеявенда общей мощностью 1014 км среди которых в эрозионном окне выступает глубокометаморфизованный дорифейский фундамент отложения которого объединяются в тараташский гранулитовый комплекс мощностью более 5 км сложенный гиперстеновыми плагиогнейсами и амфиболитами. Рифейсковендский комплекс парастратотипический для рифея разделяется на 3 эратемы снизу вверх: бурзяний R1 общей мощностью 34 км залегающую на архее и сложенную в...
35964. Внимание и его свойства 89 KB
  Устойчивость внимания длительность сосредоточения внимания на объекте. Устойчивость внимания проявляется в способности в течение длительного времени сохранять состояние внимания на какомлибо объекте предмете деятельности не отвлекать и не ослаблять внимание. У младших школьников устойчивость внимания активно возрастает к 910 годам. Сосредоточенность внимания степень концентрации внимания на объекте.