10045

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

Доклад

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

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

Русский

2013-03-20

46 KB

23 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

49413. Проблемная разработка рациональной системы применения удобрений во Владимирской области 892.5 KB
  Проблемная разработка рациональной системы применения удобрений во Владимирской области. Производственные показатели для составления системы применения удобрений Выход навоза заготовка хранение и технология внесение органических удобрений Составление системы применения удобрений в севообороте при заданной обеспеченности 1 га пашни минеральными удобрениями...
49415. Анализ структуры и потенциальных свойств заданного материала электронной техники 730.51 KB
  Содержание: Исходные данные Общие сведения о тригональной системе Построение стереографической проекции элементов симметрии вида симметрии D3d 3m и граней общей формы. Изображение стереографических проекций граней частных простых форм Матричные представления операций симметрии 3.Доказательство возникновения новых порожденных элементов симметрии 3. Список литературы Исходные данные: l2O3 Тригональная сингония 5 исходных ступеней 3v Вид симметрии D3d 3m Элементы симметрии: 2 m 3v = 3v2h3mv3 Ī а=4.
49416. Использование нейронных сетей при определении цвета глаз будущего ребенка 468 KB
  Практическое применение нейронных сетей при определении цвета глаз будущего ребенка В области определения цвета глаз будущего ребенка использование нейросетевых технологий не применяется в данное время поэтому хотелось бы попробовать осуществить эту идею поскольку мне она кажется очень даже интересной.
49417. Получение полупроводниковой гетероструктуры с заданными характеристиками методом молекулярно-пучковой эпитаксии 634.07 KB
  Определение толщин составляющих гетероструктуру слоёв их уровня легирования. Расчёт составов эпитаксиальных слоёв гетероструктуры 1. Определение ширины запрещённой зоны эпитаксиальных слоёв: = 2. Определение составов эпитаксиальных слоёв: 1 Искомый состав слоя получается исходя из требований на изопериодичность структуры и чувствительности к определённой длине волны электромагнитного излучения.
49418. Проектирование ОГС 1.1 MB
  Датчик угла по оси стабилизации. Расчёт канала стабилизации Требуется спроектировать одноосный гиростабилизатор на базе чувствительного элемента заданного типа удовлетворяющего предъявленным ниже требованиям по точности сохранения заданного положения платформы в инерциальном пространстве при действии на неё различных возмущающих воздействий линейных и вибрационных перегрузок а также по качеству стабилизации надёжности и экономичности. Одноосные гироскопические стабилизаторы ОП применяются как для непосредственной стабилизации...
49419. Разработка конструкции блокиратора системы зажигания 3.25 MB
  Прибор может использоваться в легковых автомобилях различных моделей. Имеет три вида режимов работы. Прибор устанавливается под капотом машины, на панели около руля светодиод, который служит для отображения режима работы и показывает, что автомобиль находится под защитой автосторожа.
49420. РУКОВОДСТВО К РЕШЕНИЮ ЗАДАЧ ПО ВЫСШЕЙ МАТЕМАТИКЕ 6.42 MB
  Функции нескольких переменных. Кратные интегралы. Тройной интеграл. Однородные дифференциальные уравнения первого порядка. Разложение функций в степенные ряды. Определение комплексного числа. Показательная функция с комплексным показателем