10047

Тест Рабина-Миллера проверки чисел на простоту

Доклад

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

Тест Рабина-Миллера проверки чисел на простоту. При тестировании чисел на простоту с помощью вероятностного теста основанного на малой теореме Ферма может возникнуть ситуация когда вероятность ошибки не снижается с количеством повторений теста. В этом случае она...

Русский

2013-03-20

57 KB

41 чел.

Тест Рабина-Миллера проверки чисел на простоту.

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

В этом случае она равна единице и в результате тестирования может быть принято неверное решение. В этой связи разработаны и применяются на практике вероятностные тесты, свободные от указанного недостатка, например, тест Соловея-Штрассена. При повторении теста Соловея-Штрассена раз, вероятность неотбраковки составного числа . Существенно более эффективным вероятностным тестом является тест Рабина-Миллера.

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

Пусть - нечетное натуральное число. Тогда можно записать , где - нечетное и .  Если число - простое, то , при . Поэтому квадратные корни из единицы имеют вид:, где показатель равен .

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

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

Если - составное, то возможны и другие случаи.

Основанный на данном замечании тест Рабина-Миллера заключается в следующем:

1) псевдослучайно выбираем вычет , проверяем условие . Если условие не выполнено, значит, - составное и работа закончена;

2) вычисляем . Если , то не исключено, что число - простое и необходимо перейти на начало, чтобы  повторить тест для другого основания;

3) вычисляем последовательно вычеты чисел , по модулю , пока не появится –1, либо не исчерпается список;

4) если –1 обнаружена в списке, то не исключено, что число - простое и необходимо перейти на начало, чтобы  повторить тест для другого основания;

5) если ни одно число из списка не сравнимо с –1, то число - составное и необходимо закончить работу.

Назовем составное число , где , - нечетно, сильно псевдопростым по основанию , если выполняется одно из двух условий: , либо в последовательности , существует число, сравнимое с –1 по модулю .

Известно, что такие составные числа, которые при соответствующих проходят тест Рабина-Миллера, существуют.

Однако можно показать, что при повторении теста Рабина-Миллера раз, вероятность неотбраковки составного числа .


 

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

33297. Элементы налогообложения и их характеристика 25.5 KB
  При построении налоговых отношений важное значение имеют элементы налога. Общепризнанные элементы налога: 1. Субъект налога налогоплательщиком и плательщиком сбора признаются юридические и физические лица на которые в соответствии с НК возложена обязанность уплачивать налоги и сборы. Согласно НК кроме налогоплательщиков действуют: налоговые агенты на которых возложены обязанности по исчислению удержанию и перечислению соответствующих налогов в бюджет; законный представитель налогоплательщика организации или физического лица ...
33298. Виды налоговых ставок и их применение в налогообложении 21.5 KB
  Виды налоговых ставок и их применение в налогообложении Ставка налога важный элемент налога который определяет величину налога на единицу обложения денежная единица дохода единица земельной площади единица измерения товара и т. Пропорциональные действуют в одинаковом процентном отношении к объекту налога без учета дифференциации его величины например действовавший в СССР до 1 июля 1990 г. Прогрессивные средняя ставка прогрессивного налога повышается по мере возрастания дохода. Регрессивные средняя ставка регрессивного налога...
33299. Права и обязанности налогоплательщиков. И налоговых агентов 25.5 KB
  И налоговых агентов. Права налогоплательщиков и налоговых агентов идентичны. получать от налоговых органов по месту учета бесплатную информацию о действующих налогах и сборах и законодательстве о налогах и сборах; 2. получать от налоговых органов и других уполномоченных государственных органов письменные разъяснения по вопросам применения налогового законодательства; 3.
33300. Права налоговых органов. Обязанности налоговых органов и их должностых лиц 23.5 KB
  Права налоговых органов. Обязанности налоговых органов и их должностых лиц. Организационная сисма управления налогами: 1общее управление а определение осн. принципов налогообложения; б разработка налог.
33301. Взыскание налогов и сборов налоговыми органами и порядок применения принудительных мер 25 KB
  Налогоплательщик обязан уплачивать законно установленные налоги и сборы а также в случае несвоевременной уплаты налога пеню. Взыскиваемые с налогоплательщика суммы в первую очередь направляются на погашение недоимки по налогам а затем пени. Неисполнение или ненадлежащее исполнение обязанности по уплате налога является основанием для направления налогоплательщику требования об уплате налога. Требование об уплате налога должно быть направлено налогоплательщику не позднее трех месяцев после наступления срока уплаты налога.
33302. Налоговые и таможенные органы РФ как участники налоговых отношений 25 KB
  Налоговые и таможенные органы РФ как участники налоговых отношений Государственная налоговая служба ГНС ведомство трехуровневое. Она состоит из центрального аппарата налоговых инспекций по субъектам Федерации и налоговых инспекций по районам и городам. Налоговые инспекции имеют право: проводить плановые и контрольные проверки на предприятиях в учреждениях организациях не реже одного раза в два года; получать от налогоплательщиков необходимые сведения по вопросам проверок; приостанавливать операции предприятий организаций и...
33303. Виды ответственности за налоговые правонарушения и основные нормы по НК РФ 30.5 KB
  № 9431 О налоговых органах РФ налоговым органам предоставлено право налагать административные штрафы на должностных лиц организаций виновных в непредставлении несвоевременном представлении или представлении по неустановленной форме бухгалтерских отчетов балансов расчетов деклараций и других документов связанных с исчислением и уплатой налогов в бюджет в размере от двух до пяти минимальных размеров оплаты труда на каждого виновного. За те же действия совершенные повторно административный штраф устанавливается в размере от пяти до...
33304. Показатели, характеризующие эффективность работы налоговых органов 25 KB
  Показатели целесообразно разделить на три группы: параметры отражающие степень участия субъекта Российской Федерации в части обеспечения поступлений в федеральный и территориальный бюджеты группа основных показателей; параметры соответствующие результатам непосредственной работы с налогоплательщиками группа дополнительных показателей; показатели отражающие условия работы налоговых органов учитывающие демографический территориальный социальный экономический и другие факторы группа конструктивных уточняющих показателей....
33305. Обжалование актов налоговых органов и действий или бездействия их должностных лиц 28 KB
  В случае обжалования актов налоговых органов действий их должностных лиц в суд по заявлению налогоплательщика плательщика сборов налогового агента исполнение обжалуемых актов совершение обжалуемых действий могут быть приостановлены судом в порядке установленном соответствующим процессуальным законодательством Российской Федерации. В случае обжалования актов налоговых органов действий их должностных лиц в вышестоящий налоговый орган по заявлению налогоплательщика плательщика сборов налогового агента исполнение обжалуемых актов...