Мубараков Булат Газинурович Построение оценок эффективности теста простоты Миллера-Рабина

Краткое описание

Мубараков Булат Газинурович Построение оценок эффективности теста простоты Миллера-Рабина
ОГЛАВЛЕНИЕ ДИССЕРТАЦИИ
кандидат наук Мубараков Булат Газинурович
1.2. Алгоритмы просеивания

1.3. Детерминированные алгоритмы

1.4. Вероятностные тесты простоты

1.5. Тесты простоты, отсекающие числа Кармайкла

1.6. Строго псевдопростые числа

1.7. Заключение по главе

Глава 2. ИССЛЕДОВАНИЕ СВИДЕТЕЛЕЙ ПРОСТОТЫ СОСТАВНЫХ ЧИСЕЛ

2.1. Улучшение оценки теста Миллера-Рабина

2.2. Формулы числа свидетелей для составных чисел

2.3. Формула для подсчета числа свидетелей произвольного составного числа

2.4. Функция частоты распределения свидетелей Гт(и)

2.5. Заключение по главе

Глава 3. СРЕДНЯЯ ЧАСТОТА РАСПРЕДЕЛЕНИЯ СВИДЕТЕЛЕЙ

В ЗАДАННЫХ ИНТЕРВАЛАХ

3.1. Расчет средней частоты для полупростых чисел

3.2. Улучшение асимптотической оценки средней вероятности частоты

3.3. Анализ полученных оценок

3.4. Заключение по главе

ГЛАВА 4. ЭКСПЕРИМЕНТАЛЬНЫЕ РАСЧЕТЫ СРЕДНЕЙ ЧАСТОТЫ ЧИСЛА СВИДЕТЕЛЕЙ

4.1. Основная теорема оценки числа нетривиальных свидетелей

4.2. Практический алгоритм подсчета средней частоты числа свидетелей

4.3. Оценка трудоемкости алгоритма подсчета средней частоты

4.4. Вычисление суммы частот по интервалам

4.5. Экспериментальные данные по оценке точности формулы Чебышева

4.6. Расчет суммы частот для полупростых чисел п = pq при фиксированном множителе р

4.7. Расчеты средней частоты по объединенным сериям

4.8. Экспериментальные данные по частоте для чисел п = ^

4.9. Средняя частота и ее оценка для составных чисел с произвольным числом простых делителей

4.10. Важные следствия из теорем 4.4, 4.5 и гипотезы

4.11. Заключение по главе

ЗАКЛЮЧЕНИЕ

БИБЛИОГРАФИЯ

ПРИЛОЖЕНИЯ. Библиотека вспомогательных программ на языке Ру1Ьоп106

7.1. Тексты программ, использованных в диссертации

7.2. Описания процедур, входящих в пакет компьютерных программ