10045

Тестирование чисел на простоту, случайные и детерминированные тесты. Тест малой теоремы Ферма

Доклад

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

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

Русский

2013-03-20

46 KB

23 чел.

Тестирование чисел на простоту, случайные и детерминированные тесты. Тест малой теоремы Ферма

При использовании асимметричных криптосистем возникает необходимость построения сверхбольших псевдослучайных простых чисел.

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

В криптографической практике подобные алгоритмы носят название тестов. В основе тестов лежат т.н. критерии простоты.

Существует два типа критериев простоты: детерминированные и вероятностные. Детерминированные тесты позволяют доказать, что тестируемое число – простое.

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

Детерминированные тесты более полезны, когда необходимо построить большое простое число, а не проверить простоту, скажем, некоторого единственного числа.

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

Примером вероятностного теста является тест на основе малой теоремы Ферма. Эта теорема утверждает, что если - простое, то для всех , взаимно простых с , выполняется условие (сравнение Ферма): . Таким образом, если условие теоремы Ферма не выполнено хотя бы для одного числа в интервале , то - составное.

Тест на основе малой теоремы Ферма заключается в следующем.

Псевдослучайно выбираем вычет , проверяем условие . Если условие не выполнено, значит, - составное. Проверяем сравнение Ферма (критерий простоты). Если оно не выполняется, то число - составное. Иначе, повторяем тест для другого значения и так далее. Тест может давать неверные результаты, т.к. существуют составные числа , для которых, при некотором выполняется условие малой теоремы Ферма, например, .

Назовем нечетное составное число псевдопростым по основанию  , если пара удовлетворяет сравнению .

Можно показать, что если существует (вообще говоря, неизвестное) основание , по которому не является псевдопростым, то при повторении теста Ферма  вероятность -кратного выполнения сравнения равна . В этом случае вероятность ошибки теста стремится к нулю с увеличением .

Следовательно, вероятность ошибки может не снижаться, лишь если является псевдопростым для всех (ненулевых) оснований. Тем не менее, такие числа существуют. Они называются числами Кармайкла. Например, числом Кармайкла является число .

Следовательно, тесту Ферма, вообще говоря, доверять нельзя. Однако этот тест является состовной частью ряда других тестов на простоту, т.к. его проверочное условие является необходимым условием простоты числа n.


 

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

16008. Использование средств массовой информации в борьбе с преступностью 374.5 KB
  Настоящее учебное пособие посвящено проблемам взаимодействия органов внутренних дел с телевидением, печатью, радио. Основываясь н.а материалах передового опыта и теоретической интерпретации данных науки, автор дает практические рекомендации по организации и повышению эффективности взаимодействия правоохранительных
16009. Конституция Украины основа стабильности конституционного строя и реформирования общества 1.45 MB
  Ю. Н. ТОДЫКА Е. В. СУПРУНЮК конституция УКРАИНЫ ОСНОВА СТАБИЛЬНОСТИ КОНСТИТУЦИОННОГО СТРОЯ И РЕФОРМИРОВАНИЯ ОБЩЕСТВА Симферополь Таврия 1997 В монографии в соответствии с курсом конституционного пра ва в юридических вузах рассматриваются основны
16010. Толкование Конституции и законов Украины. Теория и практика 2.34 MB
  В монографии с учетом современной правовой теории интерпретационной деятельности даются теория и практика толкования Конституции и законов Украины Конституционным Судом» иными субъектами права, рассматриваются виды, принципы, способы, пределы, стадии, процедуры, акты толкования Конституции и законов органом конституционной юрисдикции,
16011. Конституційне право України 2.27 MB
  Міністерство освіти і науки України Національна юридична академія України імені Ярослава Мудрого КОНСТИТУЦІЙНЕ ПРАВО УКРАЇНИ За редакцією доктора юридичних наук професора академіка Академії правових наук України Ю. М. Тодики доктора юридичних і політичних нау...
16012. Порівняльне правознавство 1.17 MB
  Підручник підготовлений відповідно до програми з порівняльного правознавства для юридичних ВУЗів України. У ньому відбиті досягнення вітчизняної та зарубіжної юридичної науки. Розглянуті особливості порівняльного правознавства як юридичної науки, поняття правової системи та правової сім’ї; викладені класифікації правових систем; наведена характеристика сучасних основних правових сімей
16013. Сравнительное правоведение 2.27 MB
  PAGE 6 Тихомиров Ю.А. Курс сравнительного правоведения. М.: Издательство НОРМА 1996. 432 с. Сведения об авторе Профессор Ю. А. Тихомиров заслуженный деятель науки Российской Федерации доктор юридических наук работает первым заместителем директора Ин...
16014. Списки и происхождение редакций Русской Правды 137.5 KB
  М.Н.Тихомиров СПИСКИ И ПРОИСХОЖДЕНИЕРЕДАКЦИЙ РУССКОЙ ПРАВДЫ 1 Русская Правда сохранилась в большом количестве свыше 110 списков XIII–XVIII вв. Все тексты Правды находятся в составе какихлибо сборников или летописей. По своим особенностям списки Правды могут быть разд
16015. Собственность и иные вещные права на земельные участки в РФ 446.5 KB
  Тихомиров М.Ю. Собственность и иные вещные права на земельные участки в РФ Издво Тихомирова М.Ю. 2006 г. Собственность и иные вещные права на земельные участки в РФ Глава I. Правовое регулирование субъекты и объекты прав на землю 1. Регулирование прав на землю ...
16016. Жилое помещение собственность и иные вещные права 291.5 KB
  Тихомиров М.Ю. Жилое помещение: собственность и иные вещные права по новому Жилищному кодексу Российской Федерации Изд. Тихомирова М.Ю. 2005 г. Жилое помещение: собственность и иные вещные права по новому Жилищному кодексу Российской Федерации Глава 1. Жилые