10046

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

Доклад

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

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

Русский

2013-03-20

38.5 KB

34 чел.

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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


 

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

52467. Декартові координати на площині 198.5 KB
  Узагальнити та систематизувати знання учнів з теми; розвивати пам’ять, логічне мислення,здібності учнів; виховувати інтерес до математики, увагу, самостійність;формувати вміння працювати.
52468. Толерантность 351.5 KB
  Дело № 1 Методическое пособие для Ученика конкурс учебных судов Пилотное издание серии Живое право в рамках проектов Развитие толерантности посредством учебных судов Гражданское образование: развитие профессионального потенциала Мозаика граждановедения Дело № 1 О фотографиях в паспорте РФ СанктПетербургский институт права имени Принца П. Конкурс был организован СанктПетербургским институтом права имени Принца П. Институтом права организуется региональный тур конкурса для СанктПетербурга и Ленинградской...
52469. СУДЕБНОЕ ЗАСЕДАНИЕ ПО УГОЛОВНОМУ ДЕЛУ 103 KB
  Целями проведения деловой игры Судебное заседание по уголовному делу являются: практическое изучение процесса судебного разбирательства его стадий; обучение правовой оценке исходной фактической правовой ситуации анализу материалов дела законодательства разработке правовой позиции по делу принятию процессуальных решений; формирование практических навыков реализации полномочий профессиональными субъектами уголовного судопроизводства в ходе судебного разбирательства составления процессуальных документов устных...
52470. Спільні властивості компонентів середовища програмування Delphi 212.5 KB
  Мета: ознайомити студентів з основними властивостями компонентів об’єктноорієнтованого середовища програмування Delphi особливостями їх застосування; порівняти методи застосування властивостей компонентів при створенні програмних продуктів; розвивати пізнавальний інтерес студентів вміння порівнювати аналізувати узагальнювати робити логічні висновки; виховувати інтерес до вивчення дисципліни як науки яка є основою для вивчення технологій розробки програмного забезпечення різного рівня здобуття умінь та навичок своєї професії...
52471. Шлях до демократії 106 KB
  З метою розвитку лідерського потенціалу учнівської молоді її громадянської ініціативи набуття нею досвіду активної та компетентної участі в громадському житті складовою частиною системи виховної роботи я вбачаю реалізацію проекту учнівського самоврядування “Шлях до демократіїâ€ результатом якого є створення “міні – республіка “Веселка†що сприяє об’єднанню зусиль для добрих і корисних справ розвитку здібностей і талантів вихованню компетентної й успішної особистості вихованню громадянина України – носія національних...
52472. З чого починається гарний день 47 KB
  Хід заняття Діти сьогодні ми здійснимо подорож у чарівний світ казок В. Як пахне казка Так дітки казка сьогодні пахне свіжістю хвойним лісом Дітисьогодні я прокинулася подивилася на сонечко та й замислилась: цікаво а з чого починається новий день Діти як ви думаєте: з чого починається новий день Все це вірно: із сонечка умивання сніданку Але давайте подумаємо якими словами ми визначаємо прихід нового дня Так ми бажаємо всім кого ми зустрічаємо доброго ранку Давайте пригадаємо якими словами зустрічає вас зранку...
52473. Чому існують день та ніч 277 KB
  Обладнання: картини з зображенням небесних світил та зоряного неба глобус атрибути до гри Сонце і місяць. Що настала вечірня пора Із настанням вечора сонечко опускається до обрію і заходить за нього надворі сутеніє стає темніше починають спалахувати зірки з'вляється Місяць. Тут зображено зоряне небо а на цій картині ми бачимо сонце далі ми бачимо Місяць та інші космічні пейзажі. Ви розглянули картини скажіть що ви побачили нове невідоме чи незрозуміле Якої форми Сонце Місяць та зорі Чи їхні розміри однакові Про що...