10045

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

Доклад

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

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

Русский

2013-03-20

46 KB

24 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

52157. АЛГОРИТМ ОФОРМЛЕНИЯ КОНСПЕКТА УРОКА ЧТЕНИЯ В ПЕРИОД ОБУЧЕНИЯ ГРАМОТЕ 45.45 KB
  чтение слогов слов текста с изученными буквами в основном выборочное с попутным проведением лексической работы грамматической и орфографической пропедевтики; беседа по картинке на основе наблюдений жизненного опыта детей прослушивание и анализ подготовленных дома рассказов развитие коммуникативной компетенции в режиме публичного монолога; повторение изученных звуков и букв признаков гласных и согласных звуков звуков парных по твердости мягкости звонкости глухости в процессе работы с демонстрационными и слоговыми таблицами...
52158. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ К СОСТАВЛЕНИЮ ПЛАНА-КОНСПЕКТА УРОКА, ЗАНЯТИЯ 29 KB
  Планконспект урока должен состоять из следующих рубрик: ТЕМА: название темы берется из календарнотематического плана. ЦЕЛЬ урока. ТИП урока: определяется исходя из целей и задач урока.
52159. Алгоритми та програмування 67.5 KB
  Поняття математичної інформаційної моделі. Поняття алгоритму. Учні повинні знати: основні етапи розв'язування задачі з використанням ЕОМ; поняття інформаційної моделі задачі; визначення вхідних даних та результатів поняття алгоритму; поняття виконавця; властивості алгоритмів; способи та форми подання алгоритмів; основні базові структури алгоритмів; сутність методу покрокової деталізації; основні Ідеї та принципи структурного програмування. Поняття про мову програмування.
52160. Алкоголь - ворог № 1 64 KB
  Мета: сформувати уявлення що алкоголізм це хвороба викликати почуття образи до алкогольних напоїв визначити причини та наслідки вживання алкоголю активізувати увагу на статистичних даних щодо вживання алкогольних напоїв навчити використовувати здобуті на виховному заході знання в практичній діяльності виховувати дбайливе ставлення до власного здоровя. Обладнання: фліпчарт листи А1 маркери мультимедійна установка рекламні плакати про вживання алкоголю клей ножиці.Інформаційне повідомлення Наслідки вживання алкоголю.Вплив...
52161. Вплив пивного алкоголізму на формування особливостей поведінки підлітка 39.5 KB
  Мета: розширити й поглибити знання учнів про шкідливий вплив пива, довести,що пивний алкоголізм-це соціальне зло і загроза здоров ю нації, показати,що вживання пива веде до деградації особистості, виховувати негативне ставлення до пива,досягти того,щоб учні усвідомили необхідність вести здоровий спосіб життя.
52162. Видатний український математик Георгій Вороний - одна з найяскравіших індивідуальностей в історії Чернігівщини 60.5 KB
  Познайомитись з життєвим шляхом та науковою спадщиною Георгія Вороного. Сьогодні ми ознайомимося із життєвим шляхом та науковою спадщиною великого математика Георгія Вороного. Вони вивчили матеріали про Георгія Вороного. Розповідь про життя і діяльність Георгія Вороного супроводжується презентацією.
52163. Амбіції та плани 2.61 MB
  So, you’ve understood that our today’s topic is «Jobs and Skills» and, what more, during lesson we are going to find out what skills a person needs to do his (her) job well, what professions are most demanded nowadays, what are the most suitable jobs for teenagers, how ambitious you are.
52164. Зелений агресор – амброзія полинолиста 100 KB
  Цілі: На прикладі амброзії полинолистої показати роль рослин в екосистемах. Тип уроку: практична робота з елементами бесіди Обладнання: гербарій амброзії полинолистої мультимедійна презентація робочий зошит Організаційний момент Мотивація навчальної діяльності Учитель. На мультимедійній дошці зявляється слайд з зображенням амброзії полинолистої Як ви здогадалися це амброзія полинолиста.Розглянути слайд презентації та гербарний екземпляр амброзії полинолистої.
52165. Північна Америка. Загальні відомості, особливості фізико-географічного положення, Історія відкриття та освоєння Північної Америки 46 KB
  Тема уроку: Північна Америка. Обладнання: атласи контурні карти стінні карти Північна Америка Карта півкуль підручник слайди для мультимедійної дошки. Отже ми починаємо вивчати материк Північна Америка. Розповідь вчителя За своєю площею 204 млн км2а з островами 244 млн км2 Північна Америка посідає третє місце серед континентів планети.