Тест Миллера — Рабина

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 17:53, 29 апреля 2016.

Определение

TemplateDifinitionIcon.svg Определение « Определение »
называется сильно псевдопростым, если
  1. , где - нечетное, - некое основание

Должно выполнятся одно из этих условий

Описание

Берем некое основание и возводим: . Возводим в квадрат пока не появится , а перед ней стоит . Если это не так, то число однозначно составное, если так - с некоторой вероятностью число является простым.

Как определить делитель некоего составного числа?

Делим на любое нечетное число - сложность - составное.