Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Вероятностный тест Миллера-Рабина

Тест на основе малой теоремы Ферма

Малая теорема Ферма утверждает, что если n простое, то выполняется условие: при всех a из {1, 2, …, n −1} имеет место сравнение

an −1 ≡ 1 (mod n) (1)

Из этой теоремы следует, что если сравнение (1) не выполнено хотя бы для одного числа a в интервале {1, 2, …, n −1}, то n — составное. Поэтому можно предложить следующий вероятностный тест простоты:

выбираем случайное число a из {1, 2, …, n −1} и проверяем с помощью алгоритма Евклида условие (a, n) = 1;

если оно не выполняется, то ответ «n — составное»;

проверяем выполнимость сравнения (1);

если сравнение не выполнено, то ответ «n — составное»;

если сравнение выполнено, то ответ неизвестен, но можно повторить тест еще раз.

Числа Кармайкла (Carmichael Numbers)

Особо плохими для теста Ферма являются так называемые числа Кармайкла. Они обладают следующим свойством: для любого a такого, что (a, n) = 1 верно

an-1=1(mod n)

 

Первые три числа Кармайкла таковы: 561, 1105, 1729. Среди первых 100000000 чисел их всего 255. Лишь недавно (1994 г.) было доказано, что таких чисел бесконечно много.

Пусть n — нечетное и n − 1 = 2 st, t — нечетное.

Если число n является простым, то при всех a > 1 выполняется сравнение

an −1 ≡ 1 (mod n)

Поэтому, рассматривая элементы { at, a 2 t, …, a 2 s −1 t } можно заметить, что либо среди них найдется равный −1 (mod n), либо at ≡ 1 (mod n).

На этом замечании основан следующий вероятностный тест простоты:

выбираем случайное число a из интервала {1, 2, …, n −1} и проверяем с помощью алгоритма Евклида условие (a, n) = 1;

если оно не выполняется, то ответ «n — составное»;

вычисляем at (mod n);

если at ≡ ±1 (mod n), то переходим к п. 1;

вычисляем a 2 t, …, a 2 s −1 t до тех пор, пока не появится −1;

если ни одно из этих чисел не равно −1, то ответ «n — составное»;

если мы достигли −1, то ответ неизвестен (и тест можно повторить еще раз).

Составное число не будет определено как составное с вероятностью 1 ⁄ 4. (см. [1]).

<== предыдущая лекция | следующая лекция ==>
Теорема Вильсона | Тест Рабина - Миллера
Поделиться с друзьями:


Дата добавления: 2013-12-13; Просмотров: 329; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.011 сек.