10046

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

Доклад

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

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

Русский

2013-03-20

38.5 KB

34 чел.

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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


 

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

66831. Молекулярна фізика. Основні формули 1.02 MB
  Сили поверхневого натягу діють на внутрішню та зовнішню поверхні трубки. Враховуючи невелику товщину стінок трубки, можна вважати радіуси кривини поверхонь рідини біля стінок капіляра однаковими за величиною всередині та ззовні трубки.
66832. ЕЛЕКТРИКА І МАГНЕТИЗМ 357.5 KB
  Змістом контрольних робіт є розв'язування певної кількості відповідних задач. Вміння розв'язувати задачі є одним з головних критеріїв оволодіння фізикою. І саме розв'язування задач викликає найбільші труднощі у студентів.
66833. Електромагнетизм. Магнітне поле електричного струму 1.27 MB
  Закон Біо-Савара-Лапласа в скалярному і векторному вигляді відповідно: де dB – магнітна індукція поля, яке створюється елементом провідника з струмом; - магнітна проникність; - магнітна постійна, яка дорівнює 410-7 Гн/м ; - вектор, який дорівнює довжині dl провідника і співпадає з напрямом струму...