10047

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

Доклад

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

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

Русский

2013-03-20

57 KB

41 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

29119. Представительство в гражданском праве (понятие, основания возникновения, ограничение полномочий представителя) 31 KB
  Сделка совершенная одним лицом представителем от имени другого лица представляемого в силу полномочия основанного на доверенности указании закона либо акте уполномоченного на то государственного органа или органа местного самоуправления непосредственно создает изменяет и прекращает гражданские права и обязанности представляемого. Основания возникновения: Доверенность Акт органов МСУ Акт государственного органа На основании закона Не являются представителями: лица действующие хотя и в чужих интересах но от собственного имени...
29120. Виды законного представительства 32.5 KB
  Виды законного представительства Представительство сделка совершенная лицом представителем от имени другого лица представляемого в силу полномочия основанного на законе доверенности акта органов государственного управления местного управления непосредственно изменяет прекращает гражданские правоотношения. Виды представительства: Законное Фактическое Добровольное Административное Виды законного представительства: Представительство родителями родители выступают от имени своего ребенка до 18 лет в защиту прав и интересов в...
29121. Представительство по доверенности (понятие и виды доверенности, сроки в доверенности) 30 KB
  Представительство по доверенности понятие и виды доверенности сроки в доверенности. Представительство сделка совершенная лицом представителем от имени другого лица представляемого в силу полномочия на основании доверенности. Три вида доверенности: генеральная доверенность для управления и распоряжения имуществом доверителя совершения всех возможных сделок и представительства перед любыми третьими лицами доверенность директора филиала. Срок действия доверенности: не может превышать 3 лет Если срок не указан в течение года...
29122. Форма доверенности и ее реквизиты. Заверение подписи физических лиц 27.5 KB
  Форма доверенности и ее реквизиты. Доверенность это Сделка Документ подтверждающий полномочия 1 лица в отношении другого лица перед 3 лицом Последствия по сделке возникают у представляемого Все действия происходят за счет представляемого Письменная форма Реквизиты доверенности: Подпись представляемого Дата выдача доверенности Если представляемый юр. К нотариально удостоверенным доверенностям приравниваются: 1 доверенности военнослужащих 2 доверенности лиц находящихся в местах лишения свободы; 3 доверенности совершеннолетних...
29123. Прекращение доверенности 25 KB
  Доверенностью признается письменное уполномочие выдаваемое одним лицом другому лицу для представительства перед третьими лицами. Прекращение доверенности: 1 истечения срока доверенности; 2 отмены доверенности лицом выдавшим ее; 3 отказа лица которому выдана доверенность; 4 прекращения юридического лица от имени которого выдана доверенность; 5 прекращения юридического лица которому выдана доверенность; 6 смерти гражданина выдавшего доверенность признания его недееспособным ограниченно дееспособным или безвестно отсутствующим; 7...
29124. Коммерческое представительство 27.5 KB
  Коммерческое представительство. Коммерческим представителем является лицо постоянно и самостоятельно представительствующее от имени предпринимателей при заключении ими договоров в сфере предпринимательской деятельности. Одновременное коммерческое представительство разных сторон в сделке допускается с согласия этих сторон и в других случаях предусмотренных законом. При этом коммерческий представитель обязан исполнять данные ему поручения с заботливостью обычного предпринимателя.
29125. Сроки в гражданском праве и их классификация 33 KB
  В зависимости от того кем устанавливаются сроки: законными зафиксированы в законах и иных нормативных актах законом установлен 3 летний общий срок исковой давности договорными устанавливаются соглашением сторон судебными устанавливаются судом арбитражным или третейским судом 2. По характеру определения сроков последние делятся: императивные они точно определены законом и не могут быть изменены по соглашению сторон; диспозитивные эти сроки хотя и предусмотрены законом но могут быть изменены соглашением сторон;...
29126. Исковая давность (понятие, сроки, применение) 28.5 KB
  Исковой давностью признается срок для защиты права по иску лица право которого нарушено. Сроки: Общий срок исковой давности 3 года для отдельных видов требований законом могут устанавливаться специальные сроки исковой давности сокращенные или более длительные по сравнению с общим сроком. Сроки исковой давности и порядок их исчисления не могут быть изменены соглашением сторон. Основания приостановления и перерыва течения сроков исковой давности устанавливаются настоящим Кодексом и иными законами.
29127. Перерыв и приостановление исковой давности. Последствия с ними связанные 30 KB
  Перерыв и приостановление исковой давности. Перерыв течения срока исковой давности предъявлением иска в установленном порядке совершением обязанным лицом действий свидетельствующих о признании долга. После перерыва течение срока исковой давности начинается заново; время истекшее до перерыва не засчитывается в новый срок. Приостановление течения срока исковой давности: если предъявлению иска препятствовало чрезвычайная и непреодолимая сила; если истец или ответчик находится в составе Вооруженных Сил переведенных на военное положение;...