10046

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

Доклад

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

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

Русский

2013-03-20

38.5 KB

34 чел.

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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


 

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

83076. Решение задач по закону нормального распределения при помощи редактора электронных таблиц MS Excel 422.04 KB
  Курсовая работа на тему экспериментальный метод в методологии исследования. Данная работа включает в себя: 4 задачи по теории вероятности, 2 задачи по закону нормального распределения, задачу по системам массового обслуживания.
83077. ИЗМЕРЕНИЕ ТЕПЛОЕМКОСТИ ТЕЛ 101 KB
  При нагревании на датчике 3 установки через каждые 4 с выводятся значения напряжения и силы тока нагревателя, что позволяет определить мощность и количество теплоты, выделившейся на нагревателе. Установка запоминает значения температуры стакана и цилиндра через каждые 4 с, строит графики зависимости...
83078. Технологический процесс построения модели в MatLab 564.5 KB
  Задачи управления: стабилизация на заданном уровне, наблюдение (определение траектории движения, перемещения объекта), настройка параметров или экспериментальное управление (достижение минимальных и максимальных параметров, постоянных во времени), программное управление (обеспечение наперед заданного поведения объекта).
83079. Анализ доходной и расходной частей федерального бюджета РФ за 2012-2014 года 341 KB
  Социально-экономические преобразования происходящие в современной России заставляют критически подойти к постулатам и стереотипам лежащим в основе экономической теории и заново осмыслить законы общественного воспроизводства отражающие связи и зависимости между различными элементами экономической системы.
83080. Розрахунок постійного та синусоїдального струму 6.57 MB
  Для отриманої схеми вибрати та вказати позитивні напрями струмів у вітках. Скласти у загальному вигляді систему рівнянь, використовуючи перший та другий закони Кірхгофа. Знайти струми в одній з віток методом еквівалентних перетворень для кожного з джерел, що діють окремо.
83082. Аналіз фінансово-господарської діяльності ТОВ «Меблі» 115.5 KB
  У процесі господарської діяльності у підприємства виникає необхідність видачі з каси готівки працівникам підприємства під звіт на господарські потреби та службові відрядження. Службовим відрядженням вважається поїздка працівника за розпорядженням керівника підприємства установи та організації...
83083. ПРОБЛЕМИ ТА ШЛЯХИ ПОКРАЩЕННЯ ІННОВАЦІЙНОЇ ДІЯЛЬНОСТІ ПІДПРИЄМСТВ 207.5 KB
  Очевидним і зрозумілим є те, що вирішення проблем активізації інноваційної діяльності головна запорука здійснення успішних ринкових реформ. Крім того, досвід розвинутих країн свідчить, що вихід з економічної кризи неможливий без активізації інноваційної діяльності.
83084. Товарна номенклатура Київського заводу шампанських вин «Столичний» 161.99 KB
  Характеристика Київського заводу шампанських вин Столичний Загальна характеристика асортименту Київський завод шампанських вин Столичний український виробник ігристих вин. Сьогодні підприємство випускає 28 видів шампанських вин 8ми різних кондицій та різних товарних ліній тихих вин.