10046

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

Доклад

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

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

Русский

2013-03-20

38.5 KB

34 чел.

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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


 

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

45060. Автобіографія. Документація з кадрово-контрактних питань 124.5 KB
  Після закінчення 1987 р. Після закінчення у 1993 р. Після закінчення коледжу у 1996 р. дотепер викладач екологічної безпеки Харківського реґіонального інституту післядипломної освіти вчителів.
45061. Довідково-інформаційні документи. Довідка, клопотання, службові записки, звіт. Складні слова в діловій українській мові 135.5 KB
  Утворення і правопис складних слів Складні слова можуть утворюватись за допомогою сполучних звуків і без них. УВАГА З цими словами не слід змішувати складних слів перша частина яких є вищий ступінь прислівника на Е: вищезгаданий нижчепідписаний. При цьому перша основа може закінчуватись: 1 на голосний звук: всюдихід кількаразовий радіокомітет; у словах із числівниками одно дво три чотири: одноденний двозначний триніжок чотирикутник; також у словах із...
45062. Державна мова – мова професійного спілкування 144.5 KB
  Поняття національної та літературної мови. Головні ознаки літературної мови. Отже основною метою нормативної дисципліни âУкраїнська мова професійного спілкуванняâ є усвідомлення системи української мови і розкриття особливостей її функціонування передусім у межах ділового і наукового стилів професійного спілкування. При цьому специфіка курсу полягатиме у тому що він спиратиметься на розмежування культурного і політичного аспектів життя мови.
45063. Поняття про функціональні стилі мови. Стилі сучасної української літературної мови у професійному спілкуванні 227.5 KB
  Стилі сучасної української літературної мови у професійному спілкуванні План Поняття про функціональні стилі мови. Стилістична диференціація сучасної української мови. Функціональні стилі української мови та сфера їх застосування. Специфіка мови професійного спілкування.
45064. Професійна сфера як інтеграція офіційно-ділового, наукового і розмовного стилів 144 KB
  Поняття професійна мова охоплює три функціональні різновиди літературної мови НАУКОВИЙ та ОФІЦІЙНОДІЛОВИЙ стилі. Дослідження історії їх становлення характеру лексичних та граматичних структурних компонентів жанрового багатства специфіки усної та писемної форм вираження основна мета курсу української мови професійного спілкування. Науковий стиль сучасної української літературної мови почав розвиватися з середини ХІХ ст. не беручи до уваги старої української мови основні традиції якої в науковому стилі втратилися в середині ХVІІІ...
45065. Українська термінологія в професійному спілкуванні, Загальнонаукова, міжгалузева і вузькоспеціальна термінологія 81 KB
  Термінологія - розділ мовознавства що вивчає терміни у цьому значенні все частіше використовують поняття термінознавство як наука що вивчає українську термінологію; 2 сукупність термінів певної мови або однієї певної галузі знання чи з усіх галузей знання. Системність термінології зумовлена двома типами звязків які надають сукупності термінів системного характеру: логічним коли між поняттями певної галузі науки існують системні звязки а вони є в кожній науці терміни що називають ці поняття мають бути системно повязаними;...
45066. Основи культури української мови 256.5 KB
  Словники у професійному мовленні. Типи словників. Роль словників у підвищенні культури мови. Таким чином точність мовлення великою мірою залежить від глибини знань інтелектуального рівня мовця та ерудиції особистості володіння логікою думки законами її мовного вираження а також від багатства активного словникового запасу мовця.
45067. Острые и транзиторные психотические расстройства (F23) 32 KB
  В этом смысле к данной группе относятся острые и отчасти затяжные реактивные психозы. Острый психоз продолжается от одной до двух недель. Психозы этой группы часто связаны со стрессом поэтому при диагностике указывают ассоциирован психоз со стрессом или нет. Острые транзиторные психозы ассоциированные со стрессом обозначались ранее как реактивные.
45068. Шизоаффективные расстройства (F25) 35 KB
  Этиология и патогенез Этиологически шизоаффективные расстройства могут рассматриваться как результат взаимодействия двусторонней генетической отягощенности по шизофрении и аффективным расстройствам. Распространенность Заболеваемость варьирует в зависимости от нозологической ориентации но меньше чем при шизофрении и аффективных расстройствах. Клиника В зависимости от нозологической ориентации данные расстройства с одинаковой успешностью относили к периодической параноидной шизофрении и атипичным вариантам аффективных психозов биполярных или...