10045

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

Доклад

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

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

Русский

2013-03-20

46 KB

23 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

69274. Діалогові вікна 45.5 KB
  В першу чергу необхідно вивчити, як можна визначити клас, похідний від CDialog. Оскільки демонстраційний додаток розділу володіє діалоговим вікном, що містить всі дані елементи управління, приступимо до його створення прямо зараз. Це буде проект додатку SDI під назвою ControlsDemo.
69275. Елементи керування 53 KB
  Щоб краще зрозуміти, як саме MFC забезпечує підтримку елементів управління ймовірно, було б цікаве розглянути процес створення елементів управління безвідносно до MFC. Звернете увагу, практично будь-який прямокутник, що відображається на екрані, здатний взаємодіяти з користувачем, є вікно.
69276. Кнопки, перемикачі 49.5 KB
  Вивчення класів елементів управління не випадково почате саме з класу кнопки, оскільки це найбільш часто використовуваний елемент управління, який присутній практично в кожному діалоговому вікні.
69277. Клас Cedit. Клас CListBox 54.5 KB
  Елемент управління поле введення (edit control), що інкапсулюється класом CEdit, є прямокутне дочірнє вікно, в якому користувач може вводити дані. Як правило, це найбільший елемент управління в додатку. Змінюючи стилі цього елементу управління, можна отримати все, що завгодно...
69278. Немодальні діалогові вікна 79 KB
  Визначення створення і контроль за тривалістю існування немодального діалогового вікна здійснюються впродовж семи етапів. Створення ресурсу шаблону діалогового вікна. Звернете увагу діалогові вікна в немодальному режимі не мають ніяких спеціальних стилів.
69279. Драйвер ODBC. Підключення до потоку даних. Запит даних 50 KB
  Система управління базами даних (DBMS — Database Management System). DBMS є програмним забезпеченням, що надає доступ до структурованих даних і забезпечує можливість маніпулювання ними. Прикладами найбільш популярних DBMS є Microsoft Access, Microsoft SQL Server...
69280. Підготовка і виконання запиту. Отримання даних. Відключення 41 KB
  Останнє, що додаток повинен зробити після підключення до джерела даних, але перш, ніж воно буде здатне здійснювати запити SQL, — це отримати дескриптор оператора (statement handle) або hstmt. Щоб отримати дескриптор hstmt, достаточш оголосити змінну типу SQLHSTMT і викликати функцію...
69281. Створення першого проекту Visual Studio 105.5 KB
  В меню File (Файл) виберіть пункти New (Створити), вкладку Project (Проект) або натиснути комбінацію клавіш Ctrl+Shift+N. У будь-якому випадку на екрані з’явиться діалогове вікно New Project (мал. 1.4), що дозволяє створювати всі типи проектів Visual Studio.
69282. Динамічний обмін даними. Функція Initlnstance 74.5 KB
  Динамічний обмін даними (DDX — Dynamic Data Exchange) — це засіб, за допомогою якого можна легко передавати дані між елементами управління діалогового вікна і змінними-членами додатку. Щоб створити змінну DDX, досить клацнути на елементі управління в ресурсах шаблону...