10046

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

Доклад

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

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

Русский

2013-03-20

38.5 KB

35 чел.

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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


 

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

5446. Оценка технико-экономических показателей ремонтно-механического цеха 231.5 KB
  Введение Рыночная экономика в современных условиях предъявляет высокие требования к организации производства и труда на промышленных предприятиях. При этом основным путем к повышению производительности труда на предприятиях отечественного машиностро...
5447. Модное слово 21 века 46.5 KB
  Модное слово 21 века То, что в языке, как и в любой среде, существует своя мода - давно не новость. Она меняется с течением времени. Немалое значение оказывает на нее, развитие новых технологий, изменения в политике, бизнесе, производстве, кул...
5448. Сравнение двух вариантов заготовки детали Вас шестерня 3.73 MB
  Введение В рамках дипломного проекта будет рассматриваться деталь Вал-шестерня. Для детали будет проведён анализ технологичности, который позволит оценить её технологичность, т.е. возможность рациональной обработки с помощью стандартных инструмент...
5449. Расчет гелиоустановки для летней душевой полевого бригадного стана, расположенного в Аргаяшском районе Челябинской области 150.04 KB
  Расчет гелиоустановки. Расчет гелиоустановки выполняем для летней душевой полевого бригадного стана, расположенного в Аргаяшском районе Челябинской области. Гелиоустановка рассчитана на работу с 15 апреля по 15 октября. Потребное количество энергии ...
5450. Разработка системы технического обслуживания секции поперечной фальцовки комбинированной фальцевальной машины 1.58 MB
  Курсовой проект посвящен разработка системы технического обслуживания секции поперечной фальцовки комбинированной фальцевальной машины. В приложении приведена спецификация на сборочные чертежи. Отечественные типографии зачастую должны самостоятельно...
5451. Расчет перемешивающего устройства и подбор мотора к нему 60.5 KB
  Задание: Подобрать перемешивающее устройство, провести его расчет и подобрать к нему мотор-редуктор по исходным данным. Исходные данные: Номинальный объём реактора Vн = 5м3 Давление в реакторе Р= 0,6 МПа Плотность жидкой фазы ...
5452. Расчет требуемой поверхности фильтрации 110 KB
  Задание: Рассчитать требуемую поверхность фильтрации на заданную производительность по водной суспензии, выбрать стандартный фильтр и определить их количество в установке. Исходные данные: Производительность по суспензии Vисх = 114 м3/сут. Концентра...
5453. История развития лизинга в России 50 KB
  История развития лизинга в России Первым и наиболее заметным фактом участия СССР в лизинговых сделках стали известные поставки на условиях ленд-лиза. Во время II Мировой войны США поставляло своим союзникам оружие, продовольствие, автомобильную те...
5454. Совершенствование процессов горячей объемной штамповки 2.48 MB
  Введение Кузнечно-штамповочное производство является одним из основных способов изготовления заготовок и деталей, сочетающим в себе высокую производительность и качество получаемых поковок. Кузнечные цеха являются основными заготовительными цехами н...