10046

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

Доклад

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

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

Русский

2013-03-20

38.5 KB

34 чел.

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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


 

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

85324. Функции традиционного народного костюма 39.08 KB
  В искусстве костюма органично соединились различные виды декоративного творчества: ткачество вышивка кружевоплетение низание шитье аппликация и изобразительное использование разнообразных материалов: тканей кожи меха лыка бисера бус блесток пуговиц шелковых лент тесьмы позумента кружев птичьих перьев речного жемчуга перламутра цветных граненных стеклышек и др. Хранителями древних традиций народного костюма у русских как и большинства других народов были крестьяне.Борева включал не только зачатки различных видов...
85325. Семиотические основы изучения народной художественной культуры 39.09 KB
  Решающим фактором народной культуры является процесс антропогенеза и происхождения народной культуры как таковой. В животном мире культуры не существует. В животном мире обнаруживаются явления которые в дальнейшем послужили основанием для формирования народной культуры.
85326. Семейно-бытовые праздники и обряды: структура, функции и художественные элементы 47.87 KB
  Понятие обычая обряда ритуала традиции Мы видим что стремлением людей ярко красиво торжественно и памятно отметить узловые события своей жизни обусловлено придание этим событиям форм праздников и обрядов. являются переломными моментами в жизни людей меняющими их отношения с окружающими дающими им новые права и предъявляющими новые требования. Что же заключается в понятии обряд В чем его сущность Почему во все времена начиная с первобытнообщинного строя люди отмечали торжественными ритуальными действиями наиболее выдающиеся события...
85327. Концепция этногенеза Л. Н. Гумилева 42.19 KB
  В основу своей теории этногенеза Гумилев положил в качестве главного постулата тезис о природнобиологическом характере этноса обусловленного тем что он является составной частью биоорганического мира планеты и возникает в определенных географоклпматических условиях.cnn же некоторое количество людей обладающих этим признаком соберется вместе объединенные одной целью если при этом они находятся в благоприятных географических условиях необходим разнообразный ландшафт появляется зародыш нового этноса начинается бурный процесс...
85328. Основные принципы формирования понятия народной художественной культуры 38.78 KB
  До сих пор понимание предметного поля каждого ил этих образований народной к остается весьма дискурсивным. Тем более что ряд наук филология история этнография искусствоведение претендовали в разные годы на всеобъемлющую роль в изучении народной культуры преувеличивая значение для последней своих проблем. Нельзя не сказать и о том что в России ситуация усугубляется за счет потерянных народной художественной культурой ориентиров развития в ХХ в.
85329. Традиционные и инновационные формы народной художественной культуры 39.23 KB
  В народной художественной культуре любого народа постоянно появляется и бытует огромное количество образований представляюших собой традиционный фольклор традиции и новых образований связанных с традиционными художественными структурами новации. В культурологии сочетанием традиции и новации обозначают две взаимозависимые стороны развития культуры в которых зафиксирована мысль о том что она содержит в себе как устойчивые так и изменчивые моменты. Глобальная характеристика культуры заключается в единстве традиции и новаторства...
85330. Поняття «норма» і «аномалія» в психології 31.92 KB
  Норма лат. В практичній психології і педагогіці сьогодні працюючими є поняття учбова норма; соціальновікова норма індивідуальна норма. Питання про аномалії в розвитку може розглядатися тільки в контексті знання про нормальні параметри цих процесів і поведінки.
85331. Полісенсорна система навчання слабочуючих дітей і комунікаційна система навчання глухих 38.93 KB
  Отже потрібно для нього створити відповідні його природі умови. У сучасній дидактичній системі навчання мови глухих дітей за принципом формування мовного спілкування С.Зиков розрізняють три форми словесної мови: дактильная усна і письмова. В якості вихідної форми мови найбільш повно відповідає природі глухого дитини використовується пальцева сприймається зором форма словесної мови дактильная форма.
85332. Психолого-педагогічні основи розвитку і освіти дітей зі складним дефектом 37.31 KB
  Залежно від структури порушення діти з поєднаними порушеннями поділяються на три основні групи. У першу входять діти з двома вираженими психофізичними порушеннями кожне з яких може викликати аномалію розвитку: сліпоглухих діти розумово відсталі глухі слабочуючі із затримкою психічного розвитку первинної. У другу групу мають одне істотне психофізичний порушення провідне і супутнє йому інше порушення виражене в слабкому ступені але помітно обтяжлива хід розвитку: розумово відсталі діти з невеликим зниженням слуху. У третю групу...